[ 구름톤 챌린지 ] 11일차 미션 - 통증 (2)

구름톤 챌린지 3주차가 시작되었습니다. 챌린지를 통해 문제 풀이 실력을 향상시킬 수 있으며, 블로그에 학습 일기도 작성하면 추가 보상도 주어지니 관심 있으시면 참여해보시는 것을 추천드립니다.

https://level.goorm.io/l/challenge/goormthon-challenge

구름LEVEL

 

문제

입력 / 출력

풀이 과정

dp 를 사용해 필요한 아이템의 최소 개수를 구했다. 현재 통증 상태가 i 일때의 필요한 아이템의 최소 개수를 구하고 dp 테이블에 기록하면서 통증 상태가 n 일때의 필요한 아이템의 최소 개수를 구했다.

통증 상태가 i-a 일 때 필요한 아이템의 개수가 딱 떨어진다면, 혹은 통증 상태가 i-b 일 때 필요한 아이템의 개수가 딱 떨어진다면 ( dp 테이블에 통증 상태가 i-a 일 때, i-b 일 때 값이 있다면 ) 통증 상태가 i 일 때 필요한 아이템의 최소 개수는 min(dp[i-a] + 1, dp[i-b] + 1) 이다.

낮은 통증 상태에서 아이템을 딱 맞게 사용할 수 있을 때 그 상태를 가져와 동적으로 기록하는 방법을 사용하면 해결할 수 있다.

import sys
input = sys.stdin.readline

n = int(input().rstrip())
a, b = map(int, input().rstrip().split())
dp = [0 for _ in range(n+1)]

for i in range(2, n+1):
	new_dp = []
	if i >= a and (i-a == 0 or dp[i-a] != 0): new_dp.append(dp[i-a] + 1)
	if i >= b and (i-b == 0 or dp[i-b] != 0): new_dp.append(dp[i-b] + 1)
	
	if len(new_dp) > 0:
		dp[i] = min(new_dp)
		
print(dp[n] if dp[n] != 0 else -1)