1965번 상자넣기

문제의 해결법

앞에 상자를 넣기 위해서는 뒤에 상자가 앞의 상자보다 더 커야 한다. 최고로 많이 넣을 수 있는 문제를 푼다고 하면, 최장증가부분수열의 문제와 같다고 볼 수 있다.

예제

1번 박스부터 시작하여 1번 박스보다 큰 모든 박스에게 +1해준다.

 

6번 박스보다 작은 것들은 1번 박스때의 숫자를 가지고 오고 큰 숫자들은 +1이거나 이전 박스까지 센 숫자 중 큰 것을 넣어준다.

 

점화식

$$dp[i][j] =
\begin{cases}
max(dp[i][i]+1, dp[i-1][j]), & \text{if }n\text{ box[i] < box[j]} \\
dp[i-1][j], & \text{if }n\text{ box[i]} \ge \text{box[j]}
\end{cases}
$$

 

소스코드

public static void main(String args[]) {

    Scanner in = new Scanner(System.in);
    int N = in.nextInt();
    int[] box = new int[1001];
    int[][] dp = new int[1001][1001];
    int ans = 1;
    for (int i = 1; i<= N; ++i) {
        box[i] = in.nextInt();
        dp[0][i] = 1;
    }

    for (int i = 1; i <= N; ++i) {
        dp[i][i] = 1;
        for (int j = i; j <= N; ++j) {
            if (box[i] < box[j])
                dp[i][j] = Math.max(dp[i][i] + 1, dp[i-1][j]);
            else
                dp[i][j] = dp[i-1][j];
            ans = Math.max(ans, dp[i][j]);
        }
    }
    System.out.print(ans);
}