[백준] 29792번 규칙적인 보스돌이 (파이썬)

문제링크: https://www.acmicpc.net/problem/29792

문제해결 아이디어

• 각각의 캐릭터당 최대 보상으로 보스를 잡는 dp를 생성하고 최대 보상값을 res에 저장
• res를 내림차순으로 정렬해서 m번째 캐릭터까지 합하여 정답출력
• 각각의 캐릭터 별로 보스를 잡는 데 걸리는 시간을 구한다.
• dp는 보스 종류, 15분(900초)로 구성한다.

소스코드

import sys
input = sys.stdin.readline

n, m, k = map(int, input().split())
# 캐릭터 개수, 하루에 사용할 캐릭터 수, 보스 종류

damage = [] # 캐릭터 데미지

for _ in range(n):
    damage.append(int(input()))

boss = [] # 체력, 보상

res = []

for _ in range(k):
    boss.append(list(map(int, input().split())))

for i in range(n):
    time = [0]
    for hp, worth in boss:
        h = hp // damage[i]
        if hp % damage[i]:
            h += 1

        time.append(h)

    dp = [[0] * (901) for _ in range(k+1)]

    for a in range(1, k+1):
        for b in range(1, 901):
            if b >= time[a]:
                dp[a][b] = max(dp[a-1][b], boss[a-1][1] + dp[a-1][b-time[a]]) # 현재보스를 잡지 않을 경우, 현재 보스를 잡을 경우(현재 보스 보상 + 걸리는 시간을 뺀 이전 보상 최대값)
            else:
                dp[a][b] = dp[a-1][b]

    res.append(dp[k][-1])

res.sort(reverse=True)

print(sum(res[:m]))