백준 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])

여담

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