[Baekjoon] 14231_박스 포장

문제(출처: https://www.acmicpc.net/problem/14231)

---

< 박스 포장 >

 

문제 풀이 

 

앞에 박스를 살펴보며 현재 박스보다 작은지 확인한다.

 

my solution (Java)

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

public class _14231_ { // 박스 포장

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());

		st = new StringTokenizer(bf.readLine());

		int arr[] = new int[n];
		int dp[] = new int[n];

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			dp[i] = 1;
		}

		for (int i = 1; i < n; i++) {
			for (int j = 0; j < i; j++) {
				if (arr[j] < arr[i]) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
		}

		int result = 0;
		for (int i = 0; i < n; i++) {
			result = Math.max(result, dp[i]);
		}
		System.out.println(result);
	}
}

변수)
n : 박스의 개수 
arr : 박스 크기 
dp : 과대 포장한 박스들
result : 과대 포장한 박스 개수 

 

박스의 개수를 입력받는다. 박스의 개수만큼 박스 크기를 입력받아 arr에 저장하고, dp를 1로 초기화한다. 배열을 탐색하며 현재 박스 크기보다 앞에 박스들이 작은지 확인한 후, 작다면 dp값을 업데이트한다. 최종 dp를 살펴보며 최댓값을 구해 출력한다. 

---

---