[백준] 29792 - 규칙적인 보스돌이

[문제]

---

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

[풀이]

---

브루트포스인줄 알았는데 M개의 캐릭터가 한정된 15분 내에 획득할 수 있는 메소의 최대값이였다.
M개의 캐릭터는 가장 쌘 캐릭터로 구성하면 되고,
15분 내 획득 가능한 메소의 최대값은 배낭문제로 해결할 수 있다.
보스 잡을 때 걸리는 시간은 올림을 하여 구해줬다.

[코드]

---

import sys
r=sys.stdin.readline

N, M, K = map(int,r().split())
damage=[]
for _ in range(N):
    damage.append(int(r()))
boss=[]
for _ in range(K):
    P, Q = map(int,r().split())
    boss.append((P,Q))

damage.sort(reverse=1)

def maxMeso(d):
    dp = [0]*901
    for p, q in boss:
        t = (p+d-1)//d
        if 900 < t: continue
        for j in range(900, 0, -1):
            if j-t >= 0 and dp[j-t] != 0:
                dp[j] = max(dp[j], dp[j-t]+q)
        dp[t] = max(dp[t], q)
    return max(dp)

ans=0
for i in range(M):
    ans+=maxMeso(damage[i])
print(ans)