체력 제한이 있어 끝까지 갈 수 없는 기묘한 다이나믹 프로그래밍(O(NHM)을 O(NM)으로 줄이는 트릭?)

E - Battles in a Row

E - Battles in a Row

 

 

n마리의 몬스터와 차례대로 싸우고자 하는데, 현재 체력 h 마력 m이 있다.

 

i번째 몬스터와 싸울때 두가지 중 하나를 선택할 수 있다.

 

1) 현재 체력이 A[i]이상일때, A[i]만큼 체력을 감소시키고 몬스터를 처치

 

2) 현재 마력이 B[i]이상일때, B[i]만큼 마력을 감소시키고 몬스터를 처치

 

n마리의 몬스터를 모두 쓰러뜨리거나, 어떤 행동도 취할 수 없으면 게임 종료

 

게임이 끝날때까지 몬스터를 쓰러뜨릴 수 있는 최대 수는?

 

-----------------------------------------------------------------------------------------------------------------------------------------

 

전형적인 dp문제라는걸 알 수 있긴한데... 문제는 체력,마력이 없으면 더 이상 진행할 수 없는데...

 

아니 n,h,m은 3000이라 O(NHM)은 안될테고... 어떻게 해야함?

 

dp[i][m]을 i마리까지 쓰러뜨렸을때, 마력이 m인 상황에서 체력의 최댓값

 

이처럼 핵심은 "dp[i][h][m] = i번까지 봤을때 쓰러뜨릴수있는 몬스터 수 최댓값 " 이런식으로만 생각하는데...

 

이게 아니고 " dp[i][m] = i번까지 봤을때 마력이 m에서 체력 h의 최댓값.." 이런식으로 차원의 값을 value로 넘겨버리자

 

해당 시점에 마력이 m이 될 수 없다면 -1로 둔다.

 

왜냐하면 체력이 0이여도 마력이 존재하면 몬스터를 잡을 수 있으니까

 

마법을 사용할지 말지 고려하여, 

 

i-1마리까지 쓰러뜨렸을때, 마법을 사용하지 않고 i번째를 쓰러뜨리면 체력은 dp[i][m] = dp[i-1][m] - A[i]

 

마법을 사용하여 몬스터를 쓰러뜨리면, 체력은 감소하지 않고 m+B[i]에서 마력만 감소하여 m이 되므로 dp[i][m] = dp[i-1][m+B[i]]

 

따라서, dp[i][m] = max(dp[i-1][m]-A[i], dp[i-1][m+B[i]])

 

여기서 마력이 최대를 넘어버리는등, 경계 조건에 주의하여 작성한다.

 

 

어떤 m에 대하여 dp[i][m] >= 0인 m이 존재한다면, i마리까지 쓰러뜨릴 수 있다는 뜻이다.

 

n,h,m = map(int,input().split())

A = [0]

for _ in range(n):
    
    a,b = map(int,input().split())
    A.append((a,b))

dp = [[-1]*(m+1) for _ in range(n+1)]

dp[0][m] = h

for i in range(1,n+1):
    
    a,b = A[i]

    for j in range(m+1):
        
        if j+b <= m:

            dp[i][j] = max(dp[i][j],dp[i-1][j] - a,dp[i-1][j+b])
        
        else:
            
            dp[i][j] = max(dp[i][j],dp[i-1][j] - a)

answer = 0

for i in range(1,n+1):
    
    for j in range(m+1):
        
        if dp[i][j] >= 0:
            
            answer = max(answer,i)

print(answer)