쉬운 계단 수
📚 문제 설명
N 개의 물건이 있다. 각각의 물건은 W의 무게와 V의 가치가 있다.
이 물건들을 K 무게의 가방에 담으려고 할 때, V의 합이 최대가 되도록 가방에 담으면 최대 몇인가?
👨🏻💻 풀이 과정
이 문제를 해결하는데 2가지 방법으로 진행했다.
- 2차원 배열을 활용하는 방법.
- 1차원 배열을 활용하는 방법.
우선 두 방법 모두 K 길이 만큼의 배열을 이용하여 각각의 무게에서의 V 합의 최댓값을 저장한다는 점에서 동일하다.
💡2차원 배열
N + 1 * K + 1 크기의 배열을 생성하여
각각의 행은 짐을 하나씩 추가했을 때를 의미하고
각각의 열은 해당 무게의 최대 가치를 의미한다.
결국, dp[i][j]는 i번째 짐까지 추가했을 때 무게 j의 최대 가치를 의미한다.
예를들어
N= 3K= 5 이고 각각의 짐은[1,4][2,3][3,2]인 경우.
DP는 아래와 같이 생성을 한다.
0 1 2 3 4 5 0번째 0 0 0 0 0 0 첫번째 짐 0 0 0 0 0 0 두번째 짐 0 0 0 0 0 0 세번째 짐 0 0 0 0 0 0 그리고 첫번째 짐을 추가하면 다음과 같이 갱신한다.
dp[i][j]는j에서 내 무게만큼 빼줬을 때의 최댓값에서 내 무게를 더한 값과 이전의 최댓값 중 더 큰값으로 갱신해준다.
따라서dp[i][j]=Math.max(dp[i - 1][j - MASS] + HAPPY, dp[i - 1][j])이다.
단, j에서 내 무게를 뺀 값이 음수라면, 원래 값을 그대로.
0 1 2 3 4 5 0번째 0 0 0 0 0 0 첫번째 짐 0 4 4 4 4 4 두번째 짐 0 0 0 0 0 0 세번째 짐 0 0 0 0 0 0 두번쨰 짐 추가
0 1 2 3 4 5 0번째 0 0 0 0 0 0 첫번째 짐 0 4 4 4 4 4 두번째 짐 0 4 4 7 7 7 세번째 짐 0 0 0 0 0 0 세번쨰 짐 추가
0 1 2 3 4 5 0번째 0 0 0 0 0 0 첫번째 짐 0 4 4 4 4 4 두번째 짐 0 4 4 7 7 7 세번째 짐 0 4 4 7 7 7 따라서 최댓값은
N행K열에 위치한 값이 된다.
최댓값 : 7
2차원 배열 이용 코드
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
let [N, K] = input.shift().split(' ').map(Number);
const STUFFS = input.map(v => v.split(' ').map(Number));
let dp = Array.from({length : N + 1}, () => Array.from({length : K + 1}, _ => 0));
// 물건을 하나씩 갱신.
for (let i = 1; i < STUFFS.length + 1; i++) {
const [WEIGHT, HAPPY] = STUFFS[i - 1];
for (let j = 1; j < K + 1; j++) {
// 내 값보다 j가 클 경우에만 갱신.
if (j - WEIGHT >= 0) {
dp[i][j] = Math.max(dp[i - 1][j - WEIGHT] + HAPPY, dp[i - 1][j]);
} else {
// 내 값이 더 크면 그대로.
dp[i][j] = dp[i - 1][j];
}
}
}
console.log(dp[N][K]);💡1차원 배열
1차원 배열로 푸는 방법은 위의 2차원 배열로 푸는 방식을 이해하면 생각보다 간단하다.
위와 같이 짐 목록 STUFFS를 돌며 하나씩 확인하는데,
각각의 물건의 무게 WEIGHT ~ K 까지 값을 갱신해주는 것이다.
그럼 dp[i]의 값은 i - WEIGHT 값 + HAPPY의 값과 기존의 값을 비교하여 넣어주면 된다.
1차원 배열 이용 코드
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
let [N, K] = input.shift().split(' ').map(Number);
const STUFFS = input.map(v => v.split(' ').map(Number));
let dp = new Array(K + 1).fill(0);
for (const [WEIGHT, VALUE] of STUFFS) {
for (let i = K; i >= WEIGHT ; i--) {
dp[i] = dp[i - WEIGHT] + VALUE > dp[i] ? dp[i - WEIGHT] + VALUE : dp[i];
}
}
console.log(dp[K]);🧐 후기
DP에 대해 조금 감이 잡히나 했는데 다시 멀어진 기분이다.
DP 관련 문제를 더 많이 풀어야겠다.
