백준 2293번: 동전 1 Python 풀이 및 정답 코드

문제 링크

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

2293번: 동전 1

 

 

문제 설명

문제

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

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

입력

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

출력

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

 

 

문제 풀이

고딩때 많이 풀었던... 확통 문제...
이런 문제는 같은 형식이어도 컴퓨터 입장에서 계산하도록 하는게 어렵다.

어떻게 풀어야할지 감이 잘 안와서 블로그에서 힌트를 얻었다.

 

 

 

코드

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

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

print(dp[k])

 

 

결과

통과

 

 

다른 사람의 코드

https://mong9data.tistory.com/68

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

 

 

리뷰