[백준 1965] 상자넣기

 

어려웠던 부분

• 점화식 세우는 부분
  • 점화식을 세울 때, 상자를 담을 수 있을때와 없을때를 구분해서 dp값을 갱신해야겠다고 생각했다.
    하지만, dp[현재상자]의 값을 dp[담을 수 없는 상자]로 갱신하여 dp의 값이 현재까지 증가하는 부분수열의 최대 길이를 의미하게 만들었다. 그러면, 이후에 현재상자보다 큰 상자가 나왔을 때, dp[현재상자] + 1 을 하게 되므로 올바른 상자의 개수가 아니게 된다. 아래는 내가 생각했던 점화식에 대한 반례이다.

데이터

3

4

5

1

2

 

dp

1

2

3

3

4

 

• 그래서 담을 수 없는 상자인 경우 기존의 1을 그대로 유지해서 증가하는 부분 수열의 시작 부분임을 의미하게 해야한다.

구현

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

public class Solution_for_1965 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());

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

        int[] dp = new int[N];
        
        Arrays.fill(dp, 1);

        int answer = 1;
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < i; j++) {
                // 담을 수 없는 경우
                if (num[i] <= num[j]) continue;

                // 담을 수 있는 경우
                else {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }

                answer = Math.max(answer, dp[i]);
            }
        }

        System.out.println(answer);
    }
}