[백준 1965] 상자넣기 - JAVA

BOJ Link

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

 

 

 

 

 

풀이 과정

관심사는 최대 상자의 개수이다. 어떤 상자들로 최대를 만들었는지는 상관이 없다.

 

따라서,

when cost[i] > cost[0~i-1] 일 때,

dp[i] = (dp[0 ~ i-1] 중 최대 값) +1(i번째 상자 포함)로 놓았다.

 

이는 2중 for문으로 구현 가능하다.

 

 

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] dp = new int[N];

        dp[0] = 1;

        for (int i = 1; i < N; i++) {
            int prev = 0;
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i] && dp[j] > prev) prev = dp[j];

            }
            dp[i] = prev + 1;
        }

        int ans = 0;
        for (int e : dp) ans = Math.max(ans, e);

        System.out.println(ans);
    }
}