[BOJ_1965] 상자 넣기

설명

---

점화식의 구현은 쉬운 문제이나 예외 케이스를 산정하는 것이 힘들었습니다.

 

이전의 값을 기억하고 다음 값에 상자 상태 값을 넘겨줘서 푸는 형식으로 구현을 하였습니다.

 

코드

---

package BOJ.Dynamic_Programming;

import java.util.Scanner;

public class BOJ_1965 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++){
            arr[i] = sc.nextInt();
        }

        int[] dp = new int[N];
        int ans = 0;
        for (int i = 1; i < N; i++){
            for (int j = i - 1; j >= 0; j--){
                if(dp[i] < dp[j] + 1 && arr[i] > arr[j]){
                    dp[i] = dp[j] + 1;
                    ans = Math.max(ans, dp[i]);
                }
            }
        }
        System.out.println(ans + 1);
    }
}

 

1965번: 상자넣기