[BOJ] 백준 2293번 동적계획법 동전 1

백준 2293번. 동전1

---

출처 : 백준 2293번 동전 1

2293번: 동전 1

---

문제 풀이 in Python

# 백준 2293번 동전 1
n, k = map(int, input().split())
coins = list(int(input()) for _ in range(n))
dp = [1] + [0] * k

for c in coins:
    for i in range(c, k+1):
        if i >= c:
            dp[i] += dp[i-c]
print(dp[k])

 

해당 문제는 저번에 포스팅했던 프로그래머스 거스름돈 문제와 같아 설명은 생략하겠습니다.

▶ 해당 코드에 대해 의문이 있으신 분들은 위의 링크를 눌러서 확인하시기를 바라겠습니다.

 

동적계획법은 일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것으로 가능한 모든 방법을 고려해야하므로 시간상 비효율적일 수도 있다는 단점이 있습니다. 하지만, 동적계획법은 최종적인 목적지에 도달하기 전 각 구간마다 효율적인 값을 구할 수 있기에 유용하게 사용할 수 있으므로 다음에 한 번 따로 해당 알고리즘에 대해 포스팅해보는 시간을 가져보도록 하겠습니다.