[JavaScript] 백준 1535. 안녕

이 문제는 N이 크지 않아서 dfs 로 풀어도 가능하다.

다음과 같이 각 노드에 대해 뻗어 나가는 경우는 2개이다.

1. 인사를 한다

2. 인사를 안한다

트리로 나타내면 다음과 같고, 시간복잡도는 2의 N승이다.

하지만, 제한조건 N의 수가 커진다면, 시간복잡도를 만족하지 않을 수 있다.

그럼 어떻게 최적화를 할 수 있을까?

 

경우의 수를 구하는 문제에서는 배낭(Knapsack) 알고리즘으로 해결할 수 있었다.

같은 색 노드를 봤을 때 사실 인덱스(i)만 다르지 얻을 수 있는 행복과 현재 체력은 같다. 

따라서 i 번째 사람과 인사를 안할 경우 i-1번째 사람한테서 가져오면 된다.

 

하지만 i번째 일때도 경우의 수가 4개 정도 존재한다. 그 중 어떤 경우의 수에서 값을 가져와야할까?

이것까지 고려해주기 위해 dp는 1차원 배열이 아닌 2차원 배열로 만들어주어야 한다는 것을 알 수 있다.

 

풀이
w에서 얻을 수 있는 최대 행복을 나타냅니다

값 = dp[i][w] 

- i : 사람 인덱스

- w : 체력 (0-100까지의 수)

- 값 : 누적 행복

 

😥 loss : i번째 사람과 인사하면 잃은 체력

😊 gain : i번째 사람과 인사하면 얻을 행복

 

각 사람과 가능한 체력 값을 반복한다.
현재 사람의 체력 손실이 현재 남아있는 체력보다 크거나 같으면 인사할 수 없으므로 이전 사람의 값을 가져온다.
인사할 수 있다면, 인사하는 경우와 인사하지 않는 경우의 최대 행복을 계산한다.

 

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

const n = Number(input[0]);
const loss = input[1].split(" ").map(Number); // 손실될 채력
const gain = input[2].split(" ").map(Number); // 얻을 수 있는 행복

let answer = 0; // 최대로 얻을 수 있는 행복

function tree(idx, hp, score) {
  // 체력이 0 이하로 떨어지면, 최대 행복 없어짐
  if (hp <= 0) return;

  // 최대 행복 업데이트
  answer = score > answer ? score : answer;

  // 다음 사람에 대하여 인사를 할 지 말지
  if (idx + 1 < n) {
    tree(idx + 1, hp - loss[idx + 1], score + gain[idx + 1]); // 인사를 하는 경우
    tree(idx + 1, hp, score); // 인사를 안하는 경우
  }
}

tree(-1, 100, 0);

console.log(answer);