문제 설명
문제는 이 곳 링크를 참조하길 바란다.
전체 코드
def solution(n, money):
dp = [1] + [0]*n
for i in money:
for j in range(i, n+1):
if j >= i:
dp[j] += dp[j-i]
return dp[n] % 1000000007해결 방법
쉬운 거르름돈 문제가 아니다. 동적 계획법으로 메모이제이션 기법으로 풀어야 시간 초과가 나지 않는다. 결국 다른 사람 풀이를 참고해서 풀었다ㅠㅠ
다른 사람 풀이
전체적인 로직은, money 리스트를 반복문으로 돌면서 현재 선택한 동전으로 n원 이하까지의 금액(price)을 만들 수 있는 경우의 수를 dp 리스트에 넣어준다. 이 때, 만들어야 하는 금액(price)이 현재 선택한 동전보다 작은 경우는 어차피 만들 수 없으므로 생각하지 않아도 되기 때문에 price의 범위는 range(coin, n+1)로 한다.
여기서 경우의 수를 구해줄 때 dp[price - coin]의 값을 더해주는 이유는, price - coin원을 만들 수 있는 경우들 각각에 coin을 붙여준 것이 dp[price]가 되기 때문이다.
Data Engineer