[백준] 1965 상자넣기 JavaScript

혅·2024년 8월 8일

백준, 프로그래머스 -JavaScript-

목록 보기

129/215

문제

정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다. 예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법은 여러 가지가 있을 수 있다. 앞의 예에서 차례대로 크기가 1, 2, 3, 7인 상자를 선택하면 총 4개의 상자가 한 개의 상자에 들어가게 된다.

상자의 크기가 주어질 때, 한 번에 넣을 수 있는 최대의 상자 개수를 출력하는 프로그램을 작성하시오.

입력

파일의 첫 번째 줄은 상자의 개수 n (1 ≤ n ≤ 1000)을 나타낸다. 두 번째 줄에는 각 상자의 크기가 순서대로 주어진다. 상자의 크기는 1,000을 넘지 않는 자연수이다.

출력

첫째 줄에 한 줄에 넣을 수 있는 최대의 상자 개수를 출력한다.

예제 입력

8
1 6 2 5 7 3 5 6

예제 출력

내가 했던 풀이 방법

dp를 n크기의 0으로 채워진 배열로 초기화한다.
dp[0]을 1로 초기화해준다. (여기서 0번째 index는 1번째 상자를 의미한다. 첫 번째 상자가 1인 이유는 본인의 상자만 가지고 있기 때문이다.)
1번 index부터 순차적으로 순회하면서 max를 0으로 초기화해준다. 0부터 index-1까지 반복하면서 현재 체크 중인 상자보다 앞에 있으면서 크기가 작을 때, max값을 max와 dp[j] 중에 더 큰 값으로 저장해준다. (dp[j]는 앞에 있으면서 크기가 작은 상자가 넣은 상자의 갯수를 의미한다.)
0부터 index-1까지 검사해서 나온 max의 값에 1을 추가해 dp[i]에 저장해준다. 여기서 저장된 수가 최대로 넣을 수 있는 상자의 수이다. 본인도 포함해야 하므로 1을 더해주었다.
모든 연산이 끝난 뒤에 dp에 저장된 값 중 가장 큰 값이 최대의 상자 개수이다.

코드

const fs = require('fs');
let [n, boxs] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

n = Number(n);
boxs = boxs.trim().split(' ').map(Number);

dp = Array.from({ length: n }, () => 0);
dp[0] = 1;

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

console.log(Math.max(...dp));