백준 동전 1 (2293) with python

문제

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

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

입력

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

출력

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

 

풀이

다이나믹 프로그래밍을 활용하여 문제 해결

1, 주어진 가치의 합 k의 개수만큼 배열을 할당해준다

2, 이 때 문제의 정답인 경우의 수를 생각해보면 k의 값을 가지는 조합의 개수와 같다

예를 들어 2+8=10 이라면 2에 대한 경우의 수 + 8에 대한 경우의 수와 같다

즉 이전의 경우의 수들의 합을 더해나가면 정답인 k에 대한 경우의 수를 구할 수 있다

3. 따라서 동전을 하나씩 추가시키면서 k까지 배열을 순회하면서 경우의 수들을 구해준다

 

n,k=map(int,input().split())
coin=[int(input()) for _ in range(n)]
dp=[0]*(k+1) # 만들 수 있는 경우의 수
dp[0]=1 #초기값을 1로 설정해준다

for c in coin: # 동전을 하나씩 넣어준다
    for j in range(c,k+1): 

        dp[j]=dp[j]+dp[j-c]
print(dp[k])