[백준] 2629_양팔저울 (Javascript)

문제

BOJ2629_양팔저울

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const N = +input[0];
const weights = input[1].split(' ').map(Number);
const M = +input[2];
const marbles = input[3].split(' ').map(Number);

// 모든 추의 합
const maxWeight = weights.reduce((acc, cur) => (acc += cur), 0);
const dp = [Array(maxWeight + 1).fill('N')];
dp[0][weights[0]] = 'Y';

// i = 추, j = 구슬
for (let i = 1; i < N; i++) {
    // 이전 단계 dp 테이블 복사
    dp.push(JSON.parse(JSON.stringify(dp[i - 1])));
    // 현재 추의 무게에 해당하는 곳 'Y'로 변경
    dp[i][weights[i]] = 'Y';
    for (let j = 1; j <= maxWeight; j++) {
        if (dp[i - 1][j] === 'Y') {
            dp[i][j + weights[i]] = 'Y';
            dp[i][Math.abs(j - weights[i])] = 'Y';
        }
    }
}

const answer = [];
for (let marble of marbles) {
    if (marble > maxWeight) answer.push('N');
    else answer.push(dp[N - 1][marble]);
}
console.log(...answer);

시간 복잡도

이 문제는 추의 개수를 N라고 했을 때, 완전 탐색으로 풀면 $O(n!)$의 시간복잡도를 갖는다.
문제에서 $N\le30$이라고 했으므로 최악의 경우 30!번 연산을 수행한다. 15!만해도 1,307,674,368,000이니 30!은 무조건 시간 초과가 발생한다.

따라서 이 문제는 DP의 한 유형인 냅색 알고리즘(Knapsack Algorithm)과 유사한 방식으로 풀 수 있다.

풀이

우선 추가 2,3,3,3이렇게 네 개가 주어졌다고 가정해보자.
처음 dp테이블은 아래와 같이 초기화 된다.

const dp = [Array(maxWeight + 1).fill('N')];
dp[0][weights[0]] = 'Y';

	0	1	2	3	4	5	6	7	8	9	10	11
2	N	N	Y	N	N	N	N	N	N	N	N	N

그리고 반복문을 실행한다.

for (let i = 1; i < N; i++) {
    dp.push(JSON.parse(JSON.stringify(dp[i - 1])));
    dp[i][weights[i]] = 'Y';
  
    ...

이전 단계의 dp테이블을 복사해주고

dp.push(JSON.parse(JSON.stringify(dp[i - 1])));

	0	1	2	3	4	5	6	7	8	9	10	11
2	N	N	Y	N	N	N	N	N	N	N	N	N
3	N	N	Y	N	N	N	N	N	N	N	N	N

현재 추의 무게에 해당하는 곳을 Y로 바꿔준다.

p[i][weights[i]] = 'Y';

	0	1	2	3	4	5	6	7	8	9	10	11
2	N	N	Y	N	N	N	N	N	N	N	N	N
3	N	N	Y	Y	N	N	N	N	N	N	N	N

그런 다음 0부터 maxWeight 까지 반복문을 수행해주며 아래 조건들을 수행해준다.

for (let j = 1; j <= maxWeight; j++) {
        if (dp[i - 1][j] === 'Y') {
            dp[i][j + weights[i]] = 'Y';
            dp[i][Math.abs(j - weights[i])] = 'Y';
        }
    }

	0	1	2	3	4	5	6	7	8	9	10	11
2	N	N	Y	N	N	N	N	N	N	N	N	N
3	N	Y	Y	Y	N	Y	N	N	N	N	N	N

따라서 dp 테이블은 i가 1씩 증가할 때마다 아래와 같은 모양을 띈다.

초기상태

	0	1	2	3	4	5	6	7	8	9	10	11
2	N	N	Y	N	N	N	N	N	N	N	N	N

i=1

	0	1	2	3	4	5	6	7	8	9	10	11
2	N	N	Y	N	N	N	N	N	N	N	N	N
3	N	Y	Y	Y	N	Y	N	N	N	N	N	N

i=2

	0	1	2	3	4	5	6	7	8	9	10	11
2	N	N	Y	N	N	N	N	N	N	N	N	N
3	N	Y	Y	Y	N	Y	N	N	N	N	N	N
3	Y	Y	Y	Y	Y	Y	Y	N	Y	N	N	N

i=3

	0	1	2	3	4	5	6	7	8	9	10	11
2	N	N	Y	N	N	N	N	N	N	N	N	N
3	N	Y	Y	Y	N	Y	N	N	N	N	N	N
3	Y	Y	Y	Y	Y	Y	Y	N	Y	N	N	N
3	Y	Y	Y	Y	Y	Y	Y	Y	Y	Y	N	Y

이렇게 완성된 dp테이블의 마지막 행에 있는 정보를 이용하여 구슬의 무게를 판별할 수 있다.

const answer = [];
for (let marble of marbles) {
    if (marble > maxWeight) answer.push('N');
    else answer.push(dp[N - 1][marble]);
}
console.log(...answer);