문제
풀이
•
재귀를 사용 (탑다운)
•
메모이제이션 사용
•
모든 경우 다 탐색
◦
k원에서 시작해서 가능한 모든 동전을 0원이 될떄 까지 빼봄
◦
만약에 0이하로 내려가면 불가능한 경우로 간주하고 가장 큰값을 return
◦
마지막에 출력할때 불가능한 값이 나온 경우는 -1 출력
구현
import sys
sys.setrecursionlimit(100000) #파이썬 내부적으로 재귀 함수 사용에 제한이 있어 런타임 오류가 발생하는것을 해결
n, aim = map(int, input().split())
coin = [int(input()) for _ in range(n)]
mem = [-1] * (aim + 1)
def foo(cur):
if cur < 0:
return aim + 1
if cur == 0:
return 0
if mem[cur] != -1:
return mem[cur]
result = aim + 1
for c in coin:
result = min(foo(cur - c) + 1, result)
mem[cur] = result
return result
out = foo(aim)
if out >= aim + 1:
print(-1)
else :
print(out)
Python
복사
