[구름톤 챌린지 WEEK 3 - 탐색과 동적 프로그래밍] DAY 11. 통증 (2)

통증 문제는 아래 링크 DAY 8 참고

2023.08.21 - [구름/구름톤 챌린지] - [구름톤 챌린지 WEEK 2 - 완전 탐색] DAY 6 ~ 8 리뷰

DAY 11. 통증 (2)

n = int(input())
a, b = map(int, input().split())

d = [float('inf')] * (n + 1)

d[0] = 0
for i in range(2, n+1):
    if i - a >= 0:
        d[i] = min(d[i], d[i - a] + 1)
    if i - b >= 0:
        d[i] = min(d[i], d[i - b] + 1)

print(-1 if d[n] == float('inf') else d[n])

구름톤 매주 주제와 같은 유형으로 알고리즘 스터디를 진행하는데 스터디에서 풀어본 문제 중 1로 만들기 문제와 유사했다.

이 문제의 경우 최댓값 float('inf')을 dp 배열 값으로 잡아주어야 했다.

 

d[i]는 통증 수치가 i일 때, 통증 수치를 0으로 만들기 위해 필요한 아이템의 최소 개수

 

참고

2023.08.27 - [Algorithms/이코테] - [Dynamic Programming] - 다이나믹 프로그래밍이란? / 문제 1로 만들기