백준 2293번: 동전 1

백준 2293번: 동전 1

아이디어

동전 a, b, c 를 가지고 K원을 만든다고 하자. 동전 a만 사용해서 1원부터 K원까지 만드는 경우를 배열에 기록한다(가능하면 1, 불가능하면 0으로 채워질 것). 이후 동전 a와 b 둘 다 사용해서 1원부터 K원까지 만드는 경우를 배열에 기록한다. 이때 i(1<=i<=K)원을 만드는 경우의 수는, 동전 a만 사용해서 i원을 만드는 경우의 수와 동전 a, b 모두 사용해서 (i - b)원을 만드는 경우의 수를 합한 것이다(i < b인 경우는 a만 사용해서 i원을 만드는 경우의 수와 같다).

마찬가지로, 동전 a, b, c를 사용해서 i원을 만드는 경우의 수는, 동전 a, b를 사용해서 i원을 만드는 경우의 수와, 동전 a, b, c를 사용해서 (i - c)원을 만드는 경우의 수를 합한 것이다.

점화식으로 표현하면
d2[i] = d1[i] + d2[i-v] (d1: 이전 배열, d2: 새로 만들 배열, v: 현재 선택된 동전의 가치)
그림으로 확인해보자

(0원을 만드는 방법은 동전을 하나도 사용하지 않는 방법 한가지)

코드

N, K = map(int, input().split())
value = [int(input()) for _ in range(N)]

d1 = [1] + [0]*K
d2 = [1] + [0]*K

for i in range(1, K + 1):
    if i % value[0] == 0:
        d1[i] = 1

value.pop(0)

for v in value:
    for i in range(1, K + 1):
        if i < v:
            d2[i] = d1[i]
        else:
            d2[i] = d1[i] + d2[i - v]
    d1 = d2

print(d1[K])

여담

휴가 복귀 후 격리까지 하니까 한달이 사라졌다. 앞으로 열심히 풀어야지..