[백준] 2293번 동전 1 (by Python)

 

문제

https://www.acmicpc.net/problem/2293

2293번: 동전 1

 

풀이

    DP가 늘 그렇듯, 아이디어가 중요한 문제이다.

n, k = map(int, input().split())
arr = sorted([int(input()) for _ in range(n)])
ans = [0 for i in range(k + 1)]
ans[0] = 1

for i in range(1, k + 1):
    for j in arr:
        if i >= j:
            ans[i] += ans[i - j]

print(ans[k])

    만약 위와 같은 방식으로 문제를 풀려고 한다면, 값이 너무 크게 나오는 것을 확인할 수 있을 것이다. 위의 방법은 동전의 구성이 같은데 순서가 다른 경우를 따로 세기 때문이다. 그렇기 때문에 더해지는 동전의 순서를 정해주는 것이 중요하다. 다음과 같이 동전을 하나씩 추가해가며 그 값들을 더하면 arr에 할당된 순서대로 더해져서 각 값을 만들어내기 때문에 다른 구성의 개수만을 구하는 것이 가능하다.

n, k = map(int, input().split())
arr = [int(input()) for _ in range(n)]
ans = [0 for i in range(k + 1)]
ans[0] = 1

for i in arr:
    j = i
    while j <= k:
        ans[j] += ans[j - i]
        j += 1

print(ans[k])