[DP]BOJ_14002

가장 큰 증가하는 수열 찾기.

 

입력받은 수열을 저장하기 위해 배열 seq를, seq 배열의 각 원소를 최대값으로 하는 가장 긴 부분수열의 길이를 저장하기 위해 배열 dp를 만들어 사용하였다.

 

가장 짧은 증가하는 부분수열의 길이는 자기 자신, 즉 1이기 때문에 dp[1]=1로 설정하였다.

 

이후로 다음의 논리로 dp배열을 채워 넣었다.

• 만약 seq[j](j<i)의 값이 seq[i]보다 크면, dp[i]의 값은 기존 dp[i]와 dp[j]+1 중 큰 값이다.
• seq[i]=seq[j] 이면, dp[i]=dp[j]이다. dp 배열의 각 원소가 이미 'seq[i] 를 가장 큰 값으로 하는 가장 긴 증가하는 부분수열의 길이' 이기 때문이다. seq[i]=seq[j](j<i)이면 가장 긴 증가하는 부분수열의 길이 역시 dp[j]와 같을 수밖에 없다.
• seq[j]>seq[i] 이면, dp[i]는 1과 dp[i] 중 큰 값이다.

마지막 논리를 추가하기 전까지 계속 틀렸다. seq[j]가 seq[i]보다 크다면, dp[j]는 dp[i]에 하등 영향을 미치지 못하는 것이다. dp 배열의 각 원소는 'seq[i]를 가장 큰 값으로 하는 가장 긴 증가하는 부분수열의 길이' 임을 고려하지 못했다. 따라서 seq[j]>seq[i]인 경우에는 dp[i]가 'seq[i]부터 새로이 시작하는 경우' 인 1과, '반복문을 통해 이미 업데이트된 dp[i]의 값' 중 큰 값이 되어야 한다.

 

완성된 코드는 아래와 같다.

package DP;
import java.io.*;
import java.util.Stack;

public class BOJ_14002 {
    static int[] seq=new int[1001];
    static int[] dp=new int[1001];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        String[] input = br.readLine().split(" ");
        for(int i=0;i<input.length;i++){
            seq[i+1] = Integer.parseInt(input[i]);
        }
        dp[1] = 1;

        for(int i=2;i<n+1;i++){
            for(int j=1;j<i;j++){
                if(seq[j]<seq[i]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }else if(seq[j]==seq[i]){
                    dp[i]=dp[j];
                }else if(seq[j]>seq[i]){
                    dp[i] = Math.max(1,dp[i]);
                }
            }
        }

        //가장 큰 부분수열 길이 찾기
        int max = 0;
        for(int i=1;i<n+1;i++){
            max = Math.max(max,dp[i]);
        }
        System.out.println(max);

        //역추적하여 subsequence 찾기
        int value = max;
        Stack<Integer> st = new Stack<>();
        for(int i=n;i>=1;i--){
            if(dp[i]==value){
                st.push(seq[i]);
                value--;
            }
        }

        while(!st.isEmpty()){
            System.out.print(st.pop()+" ");
        }
    }
}

이 문제는 가장 길이가 긴 증가하는 부분수열 자체도 출력해야 하기에 Stack을 사용해서 해당 기능을 구현하였다.

 

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

문제점 지적, 개선점 제안은 언제나 기쁜 마음으로 받겠습니다! 감사합니다.