[python]🔥🔥2293번 동전 1

동적계획법만 드릴하고 있는 요즘 점화식이 보이지 않을 때 너무 절망적이다.

처음에 나의 방법은

완성된 경우의 수 사이에 규칙이 있을거라 생각했다.

문제의 예제인 1,2,5를 예를 들면

1 2 2 3 4 5 6 7 8 10

이렇게 완성된 경우의 수들을 보며 규칙을 찾고 싶었다.

그렇기 때문에 규칙을 찾을 수 없었다.

10원 짜리에서 5원짜리를 뺀 5원을 만드는 경우의 수에는 1,2,5를 쓴 경우의 수가 모두 포함되어 있기에 깔끔하게 사용할 수 없었다.

결국 다른 사람들 풀이를 봤다.

https://mong9data.tistory.com/68

나처럼 한번에 경우의 수를 만드는것이 아닌, 동전 하나하나 순차적으로 만드는 것이었다.

 

1 1 1 1 1 1 1 1 1 1 1 동전 1로 만들수 있는 경우의 수
1 1 2 2 3 3 4 4 5 5 6 동전 1과 2
1 1 2 2 3 4 5 6 7 8 10 동전 1,2,3

coins,ttl = map(int,input().split())
stg = []
for i in range(coins):
    stg.append(int(input()))
dp = [0 for i in range(ttl+1)] #0의 자리를 남기기 위해
dp[0] = 1  #동전 하나로 금액을 맞출때
for i in stg:
    for j in range(i,ttl+1):
        dp[j]+=dp[j-i] #메모지제이션
print(dp[ttl])