[백준] 1965 상자넣기 (JAVA) - DP 풀이

문제 분석

• 앞에 있는 상자 크기가 뒤에 있는 상자 크기보다 작으면, 뒤에 있는 상자 안에 앞 상자를 넣을 수 있음
• 한번에 넣을 수 있는 최대 상자 갯수를 출력하기
• 상자 순서는 변경할 수 없다.

 

의사 결정

• 상자의 크기를 비교하면서 한번에 넣을 수 있는 상자 갯수를 저장하고, 갯수의 가장 큰 값을 출력하는 방식을 사용했습니다.

 

코드 구현

1. 상자의 갯수와 크기 입력, 배열에 상자 크기 저장

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] a = new int[N+1];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=1 ; i<N+1 ; i++) {
			a[i] = Integer.parseInt(st.nextToken());
		}

 

 

2. 상자 크기를 비교하며 최대 갯수 계산

한번에 넣을 수 있는 상자 개수를 저장할 배열을 선언했습니다.

 

• 이중 for문 사용

상자 a[i]를 기준으로 크기가 작은 상자 a[j]를 찾고, a[j]가 포함된 최대 상자 수를 기반으로 count 값을 갱신했습니다.

 

• 조건문

1. a[j] < a[i] : i번째 상자가 j번째 상자보다 커야함
2. count[j] >= count[i] : j번째 상자를 포함한 상자들의 수가 i번째 상자보다 많거나 같아야함

i가 4일 때, 상자 크기 1의 최대 갯수가 4에 덮어씌워지는 것을 방지하기 위해 해당 조건문을 추가했습니다. 

		int[] count = new int[N+1]; // 상자 크기 별로 한번에 넣을 수 있는 개수 저장
		count[0] = 0;
		for(int i=1 ; i<N+1 ; i++) { // 기준 상자
			for(int j=0 ; j<i ; j++) { // 비교 대상 상자		
				if(a[j] < a[i] && count[j] >= count[i]) 
					count[i] = count[j] + 1;
			}
		}

 

 

3. 결과 출력

count 배열에서 가장 큰 값을 찾아 출력했습니다.

		int max = -1;
		for(int num : count) {
			max = Math.max(num, max);
		}
		
		System.out.print(max);

 

 

전체 코드

package Baekjoon.sliver;
import java.util.*;
import java.io.*;
public class bj1965 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] a = new int[N+1];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=1 ; i<N+1 ; i++) {
			a[i] = Integer.parseInt(st.nextToken());
		}
		
		int[] count = new int[N+1]; // 상자 크기 별로 한번에 넣을 수 있는 개수 저장
		count[0] = 0;
		for(int i=1 ; i<N+1 ; i++) { // 기준 상자
			for(int j=0 ; j<i ; j++) { // 비교 대상 상자
				
				if(a[j] < a[i] && count[j] >= count[i]) 
					count[i] = count[j] + 1;
			}
		}
		
		int max = -1;
		for(int num : count) {
			max = Math.max(num, max);
		}
		
		System.out.print(max);
	}
}