[백준] S2 14231번 박스 포장 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

14231번: 박스 포장

[문제] 

영선이는 과대 포장으로 유명한 남규 회사에서 아르바이트를 한다. 영선이는 여러 박스들을 여러겹으로 포장하는 업무를 맡았다. 박스를 포장할 때 규칙이 있는데, 일단 박스를 일렬로 주어진다. 그리고 앞에 있는 박스가 뒤에 있는 박스보다 작아야지만, 뒤에 있는 박스에 넣을 수 있다. 뒤에 있는 박스를 앞에 있는 박스에 넣을 순 없다.

박스의 크기가 앞에서부터 일렬로 주어졌을 때, 최대한 박스안에 박스를 넣어 과대 포장한 박스 개수를 구하시오.

[입력]

첫째 줄에는 박스의 개수 n이 주어진다.(1≤n≤5000)

다음 줄에는 박스의 크기 Ai가 앞에서부터 차례대로 주어진다.(1≤Ai≤100,000)

[출력]

최대한 박스안에 박스를 넣어 과대 포장을 할 때, 그 박스들의 개수를 구하시오.

 

---

[풀이]

1. 입력을 받아 map 배열을 채워준다.

2. 결과를 출력하기 위한 result 변수를 선언해준다.

3. 시작은 무조건 1이므로 dp배열을 1로 채워준다.

4. 현재 값 이전까지 값들을 비교해서 더 작은 값을 찾아준다.

5. 더 작은 값이 나오면 해당 번째의 dp 배열의 값 + 1과 현재 dp 배열의 값을 비교하여 더 큰 것으로 갱신해준다.

6. result에 최댓값을 갱신해준다.

7. 모든 배열을 탐색하고 나면 결과를 출력해준다.

[접근]

1. 백준의 상자넣기 문제와 동일하게 해결하면 되겠다고 생각하였다.

2022.06.07 - [문제 풀이/Baekjoon] - [백준] S2 1965번 상자넣기 (JAVA)

[백준] S2 1965번 상자넣기 (JAVA)

[코드]

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

public class Main {
	static int n;
	static int[] arr;
	static int[] dp;
	static int check;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		arr = new int[n + 1];
		dp = new int[n + 1];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for (int i = 1; i <= n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int result = 0;
		for (int i = 1; i <= n; i++) {
			// 시작은 1
			dp[i] = 1;
			for (int j = 1; j < i; j++) {
				// 시작값과 이전값들을 비교
				// 이전 값이 크다면
				if (arr[j] < arr[i]) {
					// 현재 길이와 이전까지 연결된 최대길이 + 1과 비교해서 최대값을 갱신
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
			// 최대 크기 구하기
			result = Math.max(result, dp[i]);
		}
		
		System.out.println(result);
	}
}