[백준 1535] 안녕

문제

https://www.acmicpc.net/problem/1535

코드

const fs = require("fs");
const input = fs.readFileSync(0, "utf8").trim().split("\n");

//곡개수, 시작 볼륨, 맥스볼륨
//const [N, S, M] = input[0].split(" "); 일때 잘못 나온 이유 확인해보기

const N = Number(input[0]);
const costs = input[1].split(" ").map(Number);
const gains = input[2].split(" ").map(Number);

//최대 체력은 100이므로
// hp[소모하는 체력] = 그 체력에서 얻을 수 있는 최대 이득 
const hp = Array(100).fill(0);

for (let i = 0; i < N; i++) {
    for (let j = 99; j >= 1; j--) {
        if (j - costs[i] > 0) {
            hp[j] = Math.max(hp[j], hp[j - costs[i]] + gains[i])
        }
    }
}
// 

console.log(hp)

//j는 남은 hp
// for (let j = 100; j >= 1; j--) {
//     let maxWeight = 0
//     //i번째 사람
//     for (let i = 0; i < N; i++) {
//         if (j - costs[i] > 0) {
//             maxWeight = Math.max(hp[j], hp[j - costs[i]] + gains[i])
//         }
//     }
//     hp[j-1] = maxWeight
// }

사고과정

• 처음에는 그리디하게 풀려고 했는데, DP문제의 특징은 현재 상태가 바로 이전상태에 의존하므로 경우의 수를 떠올리면 완전탐색을 해야하고 그러면 시간 복잡도가 O( 2^N)이 되는 경우가 있다.
• 그래서 모든 경우를 계산을 하지만 타뷸레이션을 통해 중복 계산을 줄여야 한다.
• 처음에 조합으로 생각을 했더니 DP테이블을 어떻게 정의해야하는지 굉장히 곤란했는데, 이런 조합론적 상태를 고려해야하는경우 이중 반복문으로 해결할 수 있다.
  1. 전체요소에 반복문을 적용하고 하나를 선택 : for(let i =0 ;i<N;i++)
  2. 다른 요소에 대해 반복문을 돌리면서 포함 비포함을 선택
  3. 위 과정을 반복하면 조합식처럼 여러가지 경우의 수를 나눌 필요가 없이 생각할 수 있다.
  4. "복잡한 조합 문제를 한 번에 풀려고 하면 DP 테이블 정의가 어렵다.
     대신, 이 문제를 N개의 '순차적인 단계'로 쪼개어 (바깥 루프 i), 각 단계마다 모든 가능한 상태(j)를 갱신하면 (안쪽 루프 j), 복잡했던 '포함/비포함' 조합 결정이 단순한 2지선다로 해결된다."

이 알고리즘을 떠올릴 수 있는 이유

• 현재 상태가 바로 직전 상태에 영향을 받는다. → 그리디하게 풀 수 없다.
• 최대값을 물어본다.
• 중복 계산이 존재한다.
• 현재상태는 직전상태에 의존적이다.