[백준] 11055. 가장 큰 증가하는 부분 수열

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

11055번: 가장 큰 증가하는 부분 수열

dp 문제이고 내가 실수한 코드는 다음과 같다.

for (int i = 1; i < n; i++) {
    for (int j = i - 1; j >= 0; j--) {
        if (input[j] < input[i]) {
            dp[i] = dp[j] + input[i];
            break;
        }
    }
}

그런데 만약 input 값이 "20 60 50 70"인 경우 반례가 된다.

 

내가 작성한 코드대로 계산하면, i가 3일 때 dp[3] = dp[2] + input[3] 으로 dp[3]이 140이 된다.

그러나 답은 dp[1] + dp[input] 으로 150이다.

 

따라서 input[i]의 값보다 작은 input[j]를 찾았으면 다 된 것이 아니라 최댓값이 더 있을 수 있으므로, 다음과 같이 i보다 작은 인덱스를 모두 살펴봐야 한다.

for (int i = 1; i < n; i++) {
    for (int j = 0; j < i; j++) {
        if (input[j] < input[i]) {
            dp[i] = Math.max(dp[i], dp[j] + input[i]);
        }
    }
}

전체 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;

import java.io.InputStreamReader;
import java.util.*;

// 시간복잡도: O(N^2) = 100,000
public class Main {

    static int n;
    static int[] input;
    static long[] dp;
    static long answer = 0;

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            input[i] = Integer.parseInt(st.nextToken());
            dp[i] = input[i];
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (input[j] < input[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + input[i]);
                }
            }
        }

        for (long i : dp) {
            answer = Math.max(answer, i);
        }
        System.out.println(answer);
    }
}

이 문제와 유사한 문제: https://www.acmicpc.net/problem/11053