[백준] JavaScript - 상자넣기 (1965)

개요

문제 이름: 상자넣기 (1965)
문제 링크: https://www.acmicpc.net/problem/1965
플랫폼: 백준
알고리즘 분류: 다이나믹 프로그래밍
소요 시간: 30분

 

문제 전문

설명

 

입출력

 

문제 풀이

해설

이 문제는 동적 계획법(Dynamic Programming, DP)을 사용하여 LIS(Longest Increasing Subsequence, 일명 '최장  증가 부분 수열')을 찾는 문제입니다.

 

문제를 요약하면 다음과 같습니다.

• 상자들이 일렬로 나열되어 있고, 순서를 유지하면서 선택해야 합니다.
• 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작을 때만 넣을 수 있습니다.
• 최대한 많은 상자를 한 번에 넣을 수 있는 개수를 구해야 합니다.

즉, 이는 주어진 수열에서 크기가 점점 커지는 부분 수열 중 가장 긴 것을 찾는 LIS 문제라고 할 수 있겠습니다. 이러한 LIS를 구하는 방법으로는 다이나믹 프로그래밍(DP)이 있습니다.

 

시도

1차 시도  (성공)

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

const n = parseInt(input[0]);
const box = input[1].split(' ').map(Number);

const dp = Array(n).fill(1);

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

const result = Math.max(...dp);
console.log(result);

코드의 주요 내용을 설명하면 다음과 같습니다.

1. 입력으로부터 데이터를 읽어옵니다.
2. 상자의 개수 n을 정수로 변환합니다.
3. 각 상자(box)의 크기를 공백으로 구분하여 map(Number)를 사용해 숫자 배열로 변환합니다.
4. DP 배열을 생성한 다음 초기화합니다. dp[i]는 i번째 상자를 마지막으로 선택했을 때 가능한 최대 상자 개수를 저장합니다.
   1. Array(n).fill(1)을 통해 초기값은 1로 설정합니다(각 상자는 최소한 자기 자신을 포함).
5. LIS 알고리즘을 적용하기 위해 두 번째 상자부터 마지막 상자까지 순회(외부 반복문)합니다.
   1. 현재 상자(i)보다 앞에 있는 모든 상자(j)를 검사(내부 반복문)합니다.
   2. if (box[i] > box[j])는 현재 상자(i)가 이전 상자(j)보다 크면, 이전 상자를 현재 상자 안에 넣을 수 있다는 뜻입니다.
   3. 이전 상자까지의 최대 개수(dp[j])에 현재 상자를 추가한 값(dp[j] + 1)과 현재까지 계산된 dp[i] 중 더 큰 값을 선택하여 dp[i]에 저장합니다.
6. dp 배열에서 Math.max(...dp)를 사용하여 최대값을 찾습니다. 이 값이 한 번에 넣을 수 있는 최대 상자 개수입니다.
7. 최종 결과를 출력합니다.

 

시간복잡도와 공간복잡도

• 시간복잡도: O(n^2)
  • 두 개의 중첩 FOR 루프가 사용되므로 시간복잡도는 O(n^2), O의 n의 2승입니다.
• 공간복잡도: O(n)
  • DP 배열 dp의 크기가 상자의 개수 n과 같으므로 공간복잡도는 O(n)입니다.

 

사용된 주요 메서드

• fill(): 배열의 시작 인덱스부터 끝 인덱스까지 지정한 값으로 채우는 메서드입니다.
• Math.max(): 주어진 숫자 중 가장 큰 값을 반환하는 메서드입니다.