백준 14002 JAVA : 가장 긴 증가하는 부분 수열 4

문제

https://www.acmicpc.net/problem/14002

14002번: 가장 긴 증가하는 부분 수열 4

 

풀이 예상

1. dp[] 배열을 활용한다. dp[i] = i번째 에서 가장 긴 증가하는 부분 수열의 개수

2. 현재 숫자에서 이전 숫자들을 보면서 dp[i]를 갱신한다.

 

ex) input

6
10 20 10 30 20 50

 

nums[] = {10, 20, 10, 30, 20, 50}

dp[] = {0, 0, 0, 0, 0. 0}

 

1) i = 0

이전 숫자가 없으므로 갱신 할 값이 없다.

 

2) i = 1

현재 숫자(20) 보다 10이 더 작으므로

dp[1] = dp[0] +1 로 갱신 해 준다.

dp[] = {0, 1, 0, 0, 0, 0}

 

3) i = 2

현재 숫자(10) 보다 작은 숫자가 없으므로 갱신할 값이 없다.

dp[] = {0, 1, 0, 0, 0, 0}

 

4) i = 3

현재숫자(30) 보다 작은 값들을 보며 값을 갱신한다.

dp[3] = max(dp[0] +1, dp[1] +1, dp[2] +1) = 2

dp[] = {0, 1, 0, 2, 0, 0}

 

5) i = 4

현재숫자(20) 보다 작은 값들을 보며 값을 갱신한다.

dp[3] = max(dp[0] +1, dp[2] +1) = 1

dp[] = {0, 1, 0, 2, 1, 0}

 

6) i = 5

현재숫자(50) 보다 작은 값들을 보며 값을 갱신한다.

dp[3] = max(dp[0] +1, dp[1] +1, dp[2] +1, dp[3] +1, dp[4] +1) = 3

dp[] = {0, 1, 0, 2, 1, 3}

 

위의 순서대로 진행했을 때, 그 중 제일 큰 수(3) + 1 이 가장 긴 증가하는 부분 수열의 길이 이고

dp[] 배열에서 뒤부터 차례로 3, 2, 1, 0 에 해당하는 숫자를 찾으면 부분 수열의 수를 알 수 있다.

dp[] = {0, 1, 0, 2, 1, 3}

nums[] = {10, 20, 10, 30, 20, 50}

 

풀이방법 (접근 방법 & 시간복잡도)

시간복잡도 => O(N^2)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[] nums;
    static int[] answer;
    static int[] dp; //i 번째에서 내가 최대 몇번째 증가하는 수 인지
    static int result;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());
        nums = new int[N];
        dp = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());

            for (int j = i-1; j >= 0 ; j--) {
                if(nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i] , dp[j]+1);
                    result = Math.max(result, dp[i]);
                }
            }

        }
        System.out.println(result+1);

        answer = new int[result+1]; //정답 저장할 배열
        for (int i = N-1; i >= 0 ; i--) {
            if(dp[i] == result) {
                answer[result] = nums[i];
                result--;
            }
        }

        for (int i = 0; i < answer.length; i++) {
            sb.append(answer[i]).append(" ");
        }
        System.out.println(sb);

        
    }
}

 

결과