[Python] [BOJ] 동전1(2293)

💡 문제 해결

1. 0으로 초기화된 K+1크기의 리스트 생성
2. 리스트의 0번째 index를 1로 설정
3. 코인의 금액에 따라 반복문 실행
4. 해당 코인보다 낮은 금액의 코인들을 사용했을 경우의 수로 dp리스트를 갱신
5. dp리스트의 N번째 index값은 N원을 만들 수 있는 경우의 수

📌 dp리스트의 0번째 index를 1으로 설정한 이유는 그 뒤의 연산이 가능하게 하기 위함
📌 작은 금액의 코인부터 경우의 수를 추가해 나가며, 큰 금액이 될 수록 해당 금액을 만드는데 필요한 경우의 수가 앞서 계산한 경우의 수를 포함한 결과가 나올 수 있게 진행

🧾 문제 설명

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

문제보기

🖨 입출력

📝 풀이

N, K = map(int, input().split())
coins = list(int(input()) for _ in range(N))

dp = [0 for _ in range(K + 1)]
dp[0] = 1

for coin in coins:
    for i in range(coin, K + 1):
        if i - coin >= 0:
            dp[i] += dp[i - coin]

print(dp[K])

• 출처: BAEKJOON Online Judge
• 링크: https://www.acmicpc.net/problem/2293