[백준] 2293 동전1 -파이썬

문제

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

2293번: 동전 1

 

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

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

 

입력

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

 

출력

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

 

---

풀이

처음에 재귀로 풀었다가 시간초과 떴다.

이전에 봤던 dp 문제와 유사했는데 넘 아무생각 없이 구현시작했다.ㅎ

 

깔끔하게 안풀려서 다른 분의 풀이를 봤다.

https://mong9data.tistory.com/68

[백준 알고리즘][파이썬/Python] 2293번: 동전 1

dp배열에는 i를 만들 수 있는 경우의 수를 저장한다.

배열을 돌며 j-c의 값을 더해준다

 

예를 들어 값이 2인 동전으로 for문을 돌고 있고 j가 5일 때

값 5를 만드는 경우의 수 = 2 동전을 사용하기 이전에 만들었던 경우의 수 (dp[j]) + 3을 만드는 경우의 수(dp[j-c])

 

3을 만드는 경우의 수는 동전 2를 사용해서 5를 만드는 경우의 수와 같기 때문이다.

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]

dp = [1] + [0]*k

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

print(dp[k])

dp문제가 익숙하지 않아 좀 오래 걸렸다.