🔴 문제
🟡 Sol
const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [_, weights, __, beads] = fs
.readFileSync(path)
.toString()
.trim()
.split('\n')
.map((it) => it.split(' ').map(Number));
const maxWeight = 40000;
const dp = Array(maxWeight + 1).fill(false);
dp[0] = true;
for (const weight of weights) {
const ans = [];
for (let i = 0; i <= maxWeight; i++) {
if (dp[i]) ans.push(i + weight, Math.abs(i - weight));
}
ans.forEach((it) => (dp[it] = true));
}
let ans = '';
for (const bead of beads) {
ans += dp[bead] ? 'Y ' : 'N ';
}
console.log(ans.trim());🟢 풀이
⏰ 소요한 시간 : -
처음에는 완전 탐색/시뮬레이션인 줄 알았는데 시간 초과/메모리 초과가 발생해서 지피티의 도움을 받았다.
확인하고자 하는구슬의 무게가 40,000 이하니까 추들을 순회하면서 40,000이하의 무게를 만들 수 있는지를 확인해주면 된다.
즉 dp[n]은 추를 통해 n의 무게를 만들 수 있는지를 체크하는 배열이다.
먼저 아무 추도 올리지 않으면 0의 무게를 만들 수 있으니 0을 true로 둔다.
그 후 가진 추들을 순회하면서 추를 사용하면 어떤 무게를 만들 수 있는지에 대해 dp 배열을 업데이트 해주면 된다.
예제처럼 내가 만약 1, 4 두 개의 무게 추를 가지고 있고, 오른쪽에 구슬이 올라갈 예정이라고 가정하자.
0부터 40,000까지 반복하면서 현재 만들 수 있는 무게 0에서 1 짜리 무게추를 더하거나 빼서 1과 -1 총2개의 무게를 만들 수 있다. 이때 음수는 절대값 처리 해준다. 이해가 안될 수 있지만 다음 경우를 알아보자..!
다시 0부터 40,000까지 반복하면서 현재 만들 수 있는 무게 0과 1에서 4 짜리 무게추를 더하거나 빼서 3과 5 두개의 무게를 만들 수 있다. 1과 4의 추를 같이 올리면 5의 구슬을 처리할 수 있고, 1과 4를 따로 올리면 그 차이값인 3의 구슬을 처리할 수 있기 때문이다.
여기서 3과 5를 만들 수있다고 해서 바로 DP 배열에 적용해버리면, 현재 만들 수 있었던 무게는 0과 1뿐이었는데 이미 4를 사용해서만든 3에서 또 4를 사용해서 1과 7을 만들게 된다. 따라서 만들 수 있는 구슬의 값을 ans배열에 넣고, 하나의 추에 대한 탐색이 끝나면 마지막에 일괄 적용해주면 된다.
🔵 Ref
