BEAKJOON / 백준 - JAVA 1965번 상자넣기

2024.08.19기준 - 실버2

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 주어진 상자들을 이용해 가장 많이 겹쳤을 때, 그 중 제일 많이 겹친 박스의 개수를 출력하는 문제입니다.

 

1. 입력된 박스를 저장하는 배열을 생성한 후 저장을 해줍니다.

// 박스의 크기를 저장하는 배열
boxes = new int[n];
for (int i = 0; i < n; i++) {
    boxes[i] = Integer.parseInt(st.nextToken());
}

 

2. 현재 박스 위치에서 최대 몇 개의 박스를 겹칠 수 있는지 저장하는 배열을 생성합니다.(dp)

// 합쳐진 박스의 개수를 저장하는 배열
count = new int[n];
count[0] = 1; // 현재 참조하는 박스도 1개의 박스이기 때문에 1로 시작

for (int i = 1; i < n; i++) {
    count[i] = search(i) + 1;
}

 

첫 번째 박스는 자기 자신도 포함하기 때문에 무조건 1로 시작을 하게 됩니다.

 

그 후 앞에서 부터 박스의 크기를 검사하며 뒤에 있는 겹친 박스의 count들 중에 들어갈 수 가장 큰 값을 리턴해줍니다.

 

리턴 해준 값에 자기 자신의 더 해 +1의 값을 저장하여 그 중 가장 큰 값을 출력해줍니다.

 

 

코드

package Main;

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

public class Main {
	
	static int n;
	static int[] boxes, count;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// 박스의 크기를 저장하는 배열
		boxes = new int[n];
		for (int i = 0; i < n; i++) {
			boxes[i] = Integer.parseInt(st.nextToken());
		}
		
		// 합쳐진 박스의 개수를 저장하는 배열
		count = new int[n];
		count[0] = 1; // 현재 참조하는 박스도 1개의 박스이기 때문에 1로 시작
		
		for (int i = 1; i < n; i++) {
			count[i] = search(i) + 1;
		}
		
		int result = 0;
		for (int num : count) {
			result = Math.max(result, num);
		}
		
		bw.write(Long.toString(result));
		bw.flush();
		bw.close();
		br.close();
	}
	
	// 합칠수 있는 박스 중 가장 많이 겹칠 수 있는 박수의 개수를 찾아주는 함수.
	private static int search(int index) {
		int max = 0;
		
		for (int i = index - 1; i >= 0; i--) {
			if (boxes[i] < boxes[index]) {
				max = Math.max(max, count[i]);
			}
		}
		
		return max;
	}
}