[BOJ/Python] 2293번 문제풀이

문제 설명

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 2^31보다 작다.

---

풀이 과정

해당 문제의 핵심은 동적 계획법이라고 한다. 동적 계획법에 대해 우선 알아보자

 

동적 계획법 (Dynamic Programming, DP)

최적화 문제를 해결하는 알고리즘으로, 아래 내용을 명심해야 한다.

• '전체의 문제'를 '부분 문제'로 잘 나누었는가? 그렇다면 전체 문제를 해결하기 위한 부분 문제의 점화식은 무엇인가?
• 부분 문제들을 해결하며 얻는 결과값을 메모이제이션하는가?
• 부분 문제의 점화식은 부분 문제들 사이의 관계를 빠짐없이 고려하는가?

 

해당 알고리즘을 바탕으로 다음과 같은 방법으로 문제를 해결할 수 있다.

• 반복문을 통해 코인을 확인
• 반복문을 통해 코인으로 1원부터 k원까지 만들 수 있는 경우의 수를 확인할 수 있음
• k원을 만드는 과정은 현재 코인 - 현재 확인 중인 수(j)의 값을 dp[j]에 더하는 방식이다.

 

import sys

n, k = map(int, sys.stdin.readline().split())
coin = [int(sys.stdin.readline()) for _ in range(n)]
dp = [0] * 10001
dp[0] = 1

# 반복문을 통해 코인을 확인
for i in coin:
    # 반복문을 통해 코인으로 1원부터 k원까지 만들 수 있는 경우의 수를 확인
    for j in range(1, k + 1):
        if j - i >= 0:
            dp[j] += dp[j - i]

print(dp[k])

 

 

[참고자료]

https://fre2-dom.tistory.com/286

https://mong9data.tistory.com/68