[백준, 자바] 11055번 - 가장 큰 증가하는 부분 수열

문제 링크
https://www.acmicpc.net/problem/11055

이 문제의 경우 기준점을 정하는 것이 중요했다.
이게 알고 나면 굉장히 간단함.
준비물

• 원본 데이터 담는 input 배열 (1차원)
• dp를 위한 dp 배열 (1차원)

dp[기준점] = Math.max(dp[기준점], dp[비교점] + input[기준점])

여기서 비교점의 범위란 1~(i-1)까지다.
기준점은 비교점을 루프로 다 돌 때까지는 변하지 않는다.
이 기준점과 비교점을 이중 for문으로 만들 수 있다.

 for (int i = 1; i <= N; i++) { // i는 j 루프동안 고정된다. 연산 시 기준점이다.
            for (int j = 1; j < i; j++) { // j는 i의 앞에 있는 배열 수들을 연산 돌린다. 항상 i보다 값이 작을 것이다.
                System.out.println("input[j] + \" and \" + input[i] = " + input[j] + " and " + input[i]);
                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.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new java.io.InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[N+1];
        int[] input = new int[N+1];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 1; i <= N; i++) {
            input[i] = Integer.parseInt(st.nextToken());
            dp[i] = input[i];
            // dp 배열을 사전 초기화해둔다.
            // {1, 100, 2, 50, 60, 3, 5, 6, 7, 8}
        }
        for (int i = 1; i <= N; i++) { // i는 j 루프동안 고정된다. 연산 시 기준점이다.
            for (int j = 1; j < i; j++) { // j는 i의 앞에 있는 배열 수들을 연산 돌린다. 항상 i보다 값이 작을 것이다.
                System.out.println("input[j] + \" and \" + input[i] = " + input[j] + " and " + input[i]);
                if (input[j] < input[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + input[i]);
                }
            }
        }

        int max = 0; // 걍 Integer.MIN_VALUE 말고 0해도됨
        for (int i : dp) {
            max = Math.max(i, max);
        }
        System.out.println(max);
    }
}

회고
2차원 배열로 선언해서 첫줄을 초기화한 다음에 j-1, i-1 식으로 접근해서 더하는 게 아닐까 생각했는데 어림도 없지.