문제
구름-그라운드 게임에는 통증이라는 시스템이 있다. 통증 수치가 높다면 게임에서 승리하기 어려워지므로, 아이템을 적절히 사용해 통증 수치를 으로 유지하는 것이 중요하다.
게임 안에는 통증 수치를 감소시켜 주는 아이템이 종류가 있다. 아이템의 이름은 이고, 각 아이템을 사용 시 각각 만큼 통증 수치를 감소시켜 준다. 각 아이템은 원하는 만큼 획득할 수 있다.
플레이어는 적과의 전투에서 피해를 입어 현재 의 통증 수치를 가지고 있다. 플레이어가 통증 수치를 으로 줄이기 위해 필요한 아이템의 최소 개수를 구해보자. 단, 사용했을 때 통증 수치가 보다 작아지는 아이템은 사용할 수 없음에 유의하시오.
코드
from sys import stdin as s
N = int(s.readline())
A, B = map(int, s.readline().split())
dp = [float('inf')] * (N + 1)
dp[0] = 0
for i in range(1, N + 1):
if i >= A:
dp[i] = min(dp[i], dp[i - A] + 1)
if i >= B:
dp[i] = min(dp[i], dp[i - B] + 1)
if dp[N] == float('inf'):
print(-1)
else:
print(dp[N])
느낀점
이 문제는 동적 다이나믹 프로그래밍(DP)를 사용하는 문제로 우선 최소값을 구해야하는 문제이니까 처음 dp값을 inf로 설정합니다.
그리고 A가 B보다 작으니 반복문안에서 if문을 돌 때 min값을 설정하는데 그래야 더 최솟값을 i >= B에서 적용이됩니다.
처음에 DP문제를 오랜만에 풀어봐서 헷갈리긴 했지만 dp문제의 기본적인 문제이므로 어떻게 활용하는지를 알면 쉽게 풀 수 있을 것 같습니다.
