[백준] 29792. 규칙적인 보스돌이 풀이 (Python, JavaScript)

29792번: 규칙적인 보스돌이

접근한 방법

이 문제는 배낭 알고리즘을 N번 수행해야 하는 문제입니다. 문제가 복잡해보일 수 있지만 배낭 알고리즘을 이해하고 있다면 풀이할 수 있습니다. 배낭 알고리즘은 제약 조건 아래에서 주어진 무게와 가치를 가진 여러 아이템 중에서 어떤 아이템을 선택하여 배낭에 담을지 결정하는 최적화 알고리즘입니다. 일반적으로 최대 가치를 얻고자 할 때 사용합니다.

 

저는 이런 변형 문제를 풀 때 헷갈리지 않도록 무게와 가치가 어느 부분에 해당하는 지를 먼저 대입해봅니다.

우선 필요한 것은 무게 배열과 가치 배열입니다. 이 문제에서는 시간이 무게에, 메소가 가치에 해당합니다.

 

시간, 즉 무게 배열을 만들어주기 위해서는 각 캐릭터별로 모든 보스의 HP를 0으로 만드는 데 걸리는 시간을 계산해서 넣어주어야 합니다.

주의할 점은 데미지의 계산이 매초 이루어진다고 했다고 조건을 명시했기 때문에 초단위 시간으로 저장해야 합니다. (저는 이 부분을 주의깊게 안보고 분단위로 만들어놓고 맞왜틀을 시전하다 헤맸네요)

 

예제2를 예시로 들어봅시다

캐릭터 데미지 10, 20으로 3마리 보스의 HP(8999, 17999, 1)를 잡는데 걸리는 시간(무게)을 계산해줍니다. 단, 여기서 계산을 한 후 나머지가 발생한다면 최종 시간에 1초를 더해주어야 합니다. 10으로 8999를 나누면 899초가 걸리고 나머지 9가 발생하기 때문에(아직 다 못잡았기 때문에) 1초를 추가해서 총 900초가 걸리는 것입니다.

 

이렇게 해서 각각 [900초, 1800초, 1초], [450초, 900초, 1초] 입니다.

보스를 잡는데 발생하는 메소(가치)는 [10, 100, 1]로 고정되어 있습니다.

 

이렇게 무게와 가치를 모두 구했으니 N번의 배낭 알고리즘을 적용하면 됩니다.

점화식은 일반적인 배낭 알고리즘과 동일합니다.

# v는 가치 배열, w는 무게 배열

# 배낭에 물건을 넣는 경우: i번째 아이템까지 고려하고 배낭의 용량이 j일 때 얻을 수 있는 최대 가치
dp[i][j] = max(dp[i - 1][j], v[i] + dp[i - 1][j - w[i]])

# 배낭에 물건을 넣지 않는 경우: 이전까지의 아이템만을 고려하여 배낭의 용량이 j일 때의 최대 가치를 유지
dp[i][j] = dp[i - 1][j]

 

캐릭터로 계산한 무게를 하나씩 순회하며 1~900초(15분)까지의 무게로 얻을 수 있는 최대 가치를 계산하여 DP테이블에 저장해줍니다.

캐릭터 별로 900초에 해당하는 테이블(table[k][900]) 값을 결괏값 배열에 넣어주고 내림차순으로 정렬하여 M개까지의 가치 합을 계산해주면 정답을 얻을 수 있습니다.

 

 

Python

import sys
input = sys.stdin.readline

n, m, k = map(int, input().split())
result = []
dmg = [int(input()) for _ in range(n)]
boss, v = [], [0] # 보스 체력, 메소(가치)
for _ in range(k):
    a, b = map(int, input().split())
    boss.append(a), v.append(b)

for i in range(n):
    w = [0] # 시간(무게)
    for hp in boss:
        time, rest = hp // dmg[i], hp % dmg[i] # 현재 보스를 잡는데 필요한 최소 초 시간, 나머지
        time += 1 if rest else 0 
        w.append(time)
    table = [[0] * 901 for _ in range(k + 1)] # DP 테이블
    for i in range(1, k + 1):
        for j in range(1, 901):
            if j >= w[i]: # i번째 시간까지 고려하고 초가 j일 때 얻을 수 있는 최대 가치
                table[i][j] = max(table[i - 1][j], v[i] + table[i - 1][j - w[i]])
            else: # 이전까지의 시간만을 고려하여 초가 j일 때의 최대 가치를 유지
                table[i][j] = table[i - 1][j]
    result.append(table[k][-1])
print(sum(sorted(result, reverse=1)[:m])) # 내림차순 정렬 후 m개 가치에 대해서만 합을 계산

JavaScript

function solution(n, m, k, dmg, bosses) {
  const result = [];
  const [boss, v] = [[], [0]];
  bosses.forEach(([hp, meso]) => {
    boss.push(hp);
    v.push(meso);
  });
  for (let i = 0; i < n; i += 1) {
    const w = [0];
    for (const hp of boss) {
      let [time, rest] = [parseInt(hp / dmg[i]), hp % dmg[i]];
      if (rest > 0) time += 1;
      w.push(time);
    }
    const table = Array.from({ length: k + 1 }, () => Array(901).fill(0));
    for (let i = 1; i <= k; i += 1) {
      for (let j = 1; j <= 900; j += 1) {
        if (j >= w[i])
          table[i][j] = Math.max(
            table[i - 1][j],
            v[i] + table[i - 1][j - w[i]]
          );
        else table[i][j] = table[i - 1][j];
      }
    }
    result.push(table[k][900]);
  }
  result.reverse();
  let maxResult = 0;
  for (let i = 0; i < m; i += 1) maxResult += result[i];
  console.log(maxResult);
}

solution(
  2,
  2,
  3,
  [10, 20],
  [
    [8999, 10],
    [17999, 100],
    [1, 1],
  ]
);