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

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

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

중복되는 연산(합)이 있기 때문에 dp를 떠올릴 수 있다. 

 

dp를 하는 과정에서 메모이제이션하는 배열을 dp 배열이라 하고, 사용자에게 입력받은 값을 input 배열이라고 한다면, input[i]가 input[i - 1]보다 작다면, 인덱스 i보다 작은 인덱스를 내림차순으로 접근하며 input[i]보다 작은 input[j]의 인덱스 j를 찾는다. 그리고 dp[i] = dp[j] + input[i]로 하면 된다. 

 

반면, input[i]가 input[i - 1]보다 크다면 오름차순이 맞기 때문에, dp[i] = dp[i - 1] + input[i]를 하면 된다.

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

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

public class Main {

    static long[] dp;
    static int[] input;
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        dp = new long[n + 1];
        input = new int[n + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            input[i + 1] = Integer.parseInt(st.nextToken());
        }

        dp[1] = input[1];
        long max = dp[1];

        for (int i = 2; i <= n; i++) {
            if (input[i] > input[i - 1]) {
                dp[i] = dp[i - 1] + input[i];
                max = Math.max(max, dp[i]);
            } else {
                int idx = findIdx(i);
                if (idx > 0) {
                    dp[i] = dp[idx] + input[i];
                    max = Math.max(max, dp[i]);
                } else {
                    dp[i] = input[i];
                    max = Math.max(max, dp[i]);
                }
            }
        }

        System.out.println(max);
    }

    private static int findIdx(int idx) {
        for (int i = idx - 1; i >= 1; i--) {
            if (input[i] < input[idx]) {
                return i;
            }
        }
        return -1;
    }
}

그런데 틀렸다.. 예제는 맞았는데.. 아무리 생각해도 반례가 생각나지 않는다. 반례를 찾지 못하고 그냥 다른 사람들의 풀이를 봤다. 대부분 다음과 같이 풀이해놨더라.

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

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

public class Main {

    static long[] dp;
    static int[] input;
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        dp = new long[n + 1];
        input = new int[n + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            input[i + 1] = Integer.parseInt(st.nextToken());
            dp[i + 1] = input[i + 1];
        }

        long max = dp[1];

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

        System.out.println(max);
    }
}

이중 for 문의 i와 j에 집중해서 보면 된다. 즉 dp[i]의 값을 채울 때 인덱스 1부터 i - 1까지 하나하나 살펴서 오름차순인 경우 dp[i]를 갱신을 시도한다. 그리고 이때 기존 dp[i]의 값과 갱신될 값을 비교하여 갱신하거나 갱신하지 않는다(Math.max(dp[i], dp[j] + input[i])).

 

기존 내가 작성한 코드가 왜 틀렸는지 생각하지 못했다. 반례를 찾는 능력이 부족한 거 같다. 그러나 내가 작성한 코드에 비해 올바른 답은 점화식이 분명하다(dp[i] = Math,max(dp[i], dp[j] + input[i])). 따라서 dp 문제인 만큼 구현 전에 점화식을 좀 더 분명히 생각했더라면, 올바른 답의 코드를 떠올릴 수 있지 않았을까? dp 문제는 점화식을 분명히 하자!

 

참고로 다음 문제와 아주 유사하니 둘 다 풀어보자.

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

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