Study/Problem Solving
[BOJ_1965] 상자 넣기
monitor
2024. 3. 14. 23:02
설명
점화식의 구현은 쉬운 문제이나 예외 케이스를 산정하는 것이 힘들었습니다.
이전의 값을 기억하고 다음 값에 상자 상태 값을 넘겨줘서 푸는 형식으로 구현을 하였습니다.
코드
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번: 상자넣기
정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가
www.acmicpc.net