알고리즘 유형 : DP(Dynamic Programming), 냅색
풀이 참고 없이 스스로 풀었나요? : △
https://www.acmicpc.net/problem/2629
소스 코드(node.js)
"use strict";
const fs = require("fs");
const input = fs.readFileSync(0).toString().trim().split("\n")
const N_w = Number(input[0])
const weight = [0].concat(input[1].split(" ").map(Number))
const N_b = Number(input[2])
const ball = input[3].split(" ").map(Number)
const knapsack = []
let max_ball = 0;
for (let i=1; i<N_w+1; i++){
max_ball += weight[i];
}
for (let i=0; i<N_w+1; i++){
knapsack.push(Array.from({length: max_ball+1}, (v, i) => ("N")));
}
for (let row=1; row<N_w+1; row++){
for (let col=1; col<max_ball+1; col++){
if (knapsack[row-1][col] === "Y"){
knapsack[row][col] = "Y";
}else if (weight[row] === col){
knapsack[row][col] = "Y";
}else{
const a = knapsack[row][col] = knapsack[row-1][Math.abs(weight[row]-col)];
const b = knapsack[row][col] = knapsack[row-1][weight[row]+col];
if (a === "Y" | b === "Y"){
knapsack[row][col] = "Y";
}else{
knapsack[row][col] = "N";
}
}
}
}
const result = [];
for (let i=0; i<ball.length; i++){
const request = ball[i];
if (request > max_ball){
result.push("N");
}else{
result.push(knapsack[N_w][request]);
}
}
console.log(result.join(" "));
for (let i=0; i<N_w+1; i++){
console.log(knapsack[i]);
}풀이 요약
- 이 문제는 냅색 알고리즘으로도 풀 수 있다. 해당 문제에서 추는 아예 안 쓸 수도 있고, 다 쓸 수도 있다. 그렇게 해서 나타낼 수 있는 모든 수 중에 입력으로 받은 공 무게가 거기에 포함되어 있는지 판별하면 되는 것이다.
-
문제를 분석해보자. 두 번째 테스트케이스를 살펴보자.
4
2 3 3 3
3
1 4 10추가 4개이고, 공의 무게가 1, 4, 10이다.
우리가 구하고자 하는 것은 추를 0~4개까지 사용해서 해당 공의 무게를 나타낼 수 있느냐는 것이다.
만약 추 4개를 활용해서(0~4개를 쓴다는 의미) 무게 8을 나타내는지 알아보고싶다면,
1)
추를 3개(2, 3, 3)를 활용해서 무게 5를 나타낼 수 있다면, 거기에다가 더 무거운 저울쪽에 4번째 추 3을 올려버리면 무게 8을 나타내는 것이므로 오케이.2)
추 3개를 활용해서 만약 무게 11을 나타낼 수 있다면, 이번에는 가벼운 저울쪽에 4번째 추 3을 올려버리면 차이가 줄어드므로 무게 8을 나타내게 된다.3) 또 다른 경우도 있는데,
추 3개를 활용해서 무게 8을 나타낼 수 있다면, 굳이 4번째 추를 이용하지 않고 추 3개만 활용하면 된다.4) 예외적인 경우로, 만약에 추가 4개(마지막 추는 무게가 4), 공 무게 3을 나타내고싶다고 해보자. 이 때는 추 3개로 공 무게 1을 나타낼 수 있는지 알아보면 된다. 더 가벼운 저울에 무게 4짜리 마지막 추를 올리면 그 차가 3이 된다. 그 외에는 뭐 위에서 설명한대로 추 3개로 무게 7을 나타낼 수 있는지, 3을 나타낼 수 있는지 등등을 알아보면 알아낼 수 있다. 더 가벼운 쪽에 추를 올리는 경우에 대해 이렇게 두 가지로 경우의 수가 갈리는 건데, 두 경우를 모두 포함하기 위해 abs(추무게 - 표현할 공무게)를 사용하면 된다.
이 3가지 경우중에 하나라도 만족하는 경우가 있다면, 추 4개를 활용해서 무게 8을 만들 수 있는 것이다. (Y)
추 4개에 대한 무게 확인 여부를, 추 3개 여부를 활용해서 구하므로 재귀 구조가 보인다. 점화식으로 나타내보자.
knapsack[row][col] = knapsack[row-1][col] or knapsack[row-1][abs(col-추무게)] or knapsack[row-1][col+추무게]
이 때, 리스트는 2차원인데, 행은 row이고 이는 0~row번째 추들을 활용하겠다는 것을 의미한다. 열은 col이고, 이는 추를 활용해서 나타내고자하는 임의의 공의 무게이다. knapsack[row][col]은 0번째~row번째 추들을 활용해서 무게 col을 나타낼 수 있는지 여부가 Y, N으로 담겨 있는 값이다. 점화식에서, 세 경우 중 하나라도 Y이면 knapsack[row][col] = Y인 것이다.
- 점화식에서 하나 더 추가해서 조건문을 넣어줄 수 있는데, 만약 row === col, 즉 추 무게와 표현하려는 공 무게가 같다면, 그 추만 하나 사용해주면 되므로 무조건 Y이다.
- 냅색 알고리즘대로 이제 구현하면 되는데, knapsack 메모이제이션 2차원 배열의 행 개수를 추의 개수보다 1개 더 많이 만들자. 추 1개일 때의 경우를 for돌면서 구할 때, row-1 인덱스를 조회하는 경우가 있기 때문이다.
- 마지막에 입력받은 공 무게들을 메모이제이션 배열에서 조회할 때, 만약 입력값이 모든 추 무게의 합보다 크면, knapsack 배열의 인덱스 범위도 넘어갈뿐만 아니라 애초에 못 만들기 때문에 "N"를 출력해줘야한다. 그 외에는 knapsack 배열 인덱싱!
배운 점, 어려웠던 점
- DP라는 건 아는 상태에서 풀었는데 못 풀었다. 문제 한 줄 설명에 냅색 알고리즘으로 풀 수 있다길래 냅색으로 풀었는데, 점화식을 조금 틀리게 작성해서 오답처리 됐었다. 다른 사람 풀이를 참고하려고 했는데 냅색으로 푼 풀이가 별로 없어서, 그냥 스스로 다시 고민해보다가 점화식(조건문)을 제대로 세우게 되었고, AC를 받았다.
- 딱 문제를 보고, 이걸 냅색 알고리즘을 적용할만한지 판단하는 능력이 부족함을 깨달았다. 곰곰히 생각해보니, 뭔가 물건을 가지고 어떤 값을 만들어야하는데, 물건을 아예 안 쓸 수도 있고 다 쓸 수도 있을 때 이를 행으로 두고, 열 같은 경우는 점화식을 생각해보면서, 해당 행에 해당하는 값을 찾기 위해 이전 행의 어떤 값을 활용하는지 알아보고, 그 변수를 열로 둬야겠으며, 그 메모이제이션 배열의 원소는 구하고자 하는 값(이 문제에선, Y나 N)이라고 나름의 정립을 했다.
