상자넣기

문제

언어

  • JavaScript

순서도

  1. 점화식을 정의하고, 그에 맞게 dp 배열 생성하기
  2. dp 배열의 base 값 정의
  3. 점화식과 base 값을 이용해서 dp 배열 채우기
  4. dp 배열의 값 중에서 최대값 출력

문제 풀이 step 1

  • 정육면체 모양의 상자가 일렬로 늘어서 있습니다.
  • 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수 있습니다.
  • 상자를 넣는 여러가지 방법 중에 한 번에 넣을 수 있는 상자 개수가 최대가 되는 경우, 그 때의 상자의 개수를 구하는 문제입니다.

문제 풀이 step 2

  • dp[n] = n 번째 상자에 한 번에 넣을 수 있는 최대의 상자 개수
  • DP의 특징인 작은 문제의 해답으로부터 큰 문제의 해답을 찾는다를 이용합니다.
  • 점화식은 “dp[n] = 1 + Math.max(dp[n - 1], dp[n - 2], … dp[0])” 입니다.
    • 단, Math.max 함수 안에 들어갈 수 있는 dp 값들은 n 번째 상자보다 작은 상자들만 가능합니다.
  • base 값은 1 입니다.
  • 우선, 점화식과 base 값을 이용해서 dp 배열을 다 채웁니다.
  • 예를 들어 dp[n] 을 구하려고 할 때,
    • dp[0] ~ dp[n - 1] 의 값 중에서,
    • n 번째 상자의 높이보다 작은 경우를 뽑고,
    • 그 중에서 최댓값을 찾은 다음에 + 1 (n 번째 상자 추가) 해주면 됩니다.
  • 추가 설명은 주석으로 작성하겠습니다.

후기

  • 본 문제의 경우에는 dp 값 자체가 모든 경우의 최대값을 의미하는 것이 아니기 때문에 마지막에 최대값을 구하는 과정이 필요했습니다.

소스 코드 1

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	const n = Number(input[0]);
	const arr = input[1].split(" ").map(Number);

	// base
	const dp = [1];
	for (let i = 1; i < n; i++) {
		let max = 0;
		// dp[0] ~ dp[n - 1] 중에서
		for (let j = 0; j < i; j++) {
			// n 번째 상자의 높이보다 작은 dp 값 중에서
			// 최댓값을 찾기
			if (arr[j] < arr[i]) max = Math.max(max, dp[j]);
		}

		dp[i] = max + 1;
	}

	// dp 값들 중에서 최댓값 구하기
	let max = 0;
	for (let i = 0; i < n; i++) {
		max = Math.max(max, dp[i]);
	}

	return max;
};

console.log(solution(input));