백준/ Gold 5 문제 , 백준 파이썬 2293 , 동전 1 [dp]

백준/ Gold 5 문제 , 백준 파이썬 2293 , 동전 1 [dp]

 

 

문제 출처

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
처음에 JS 로 풀었던 문제인데 JS로 풀 수 없는 문제라 파이썬으로 풀었다.
이 문제는 표를 그려서 경우의수들을 확인하면 더 잘 이해가 될 것이다.

 

 

 

문제 출처

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

2293번: 동전 1

 

 

 

풀이

 

 

예를 들어보자.

n=3, k=10

nums=[1, 2, 5] 일 때,

 

표를 보면서 한줄씩 이해해보자.

 

10까지의 숫자를 1로만 만들수 있는 수는 다 한가지씩 밖에 없다.  (1 가지고는 모든 수를 만들 수 있다. 10까지 다 1로 채운다.)

 

*참고로 여기 적힌 숫자는 열에 해당하는 숫자에서 행에 해당하는 숫자를 한번 빼고 남은 수를 만들 수 있는 경우의 수를 저장한것이다. 만약 왼쪽 행에 해당하는 수가 2고 열에 해당하는 숫자가 6이면 6에서 2를 뺀 4를 만들수 있는 경우의 수를 보면된다. 4 를 만들수 있는 경우의 수는 1,2 두가지가 저장되어있으므로 합해서 총 3가지이다.

 

 

그리고 2 가지고는 자기 자신 숫자인 2를 한가지의 방법으로 만들 수 있고 3은 2+1 의 방법으로 한가지로 만들수있다.

 

이때 3에서 2를 뺀 1을 보면 1을 만들 수 있는 가짓수가 1개로 위에서 설정해뒀었다. 

 

결국이 한개를 그대로 들고 오는 것과 같다.

 

4는 4-2 = 2 를 만들 수 있는 지금까지의 경우의 수들을 합하면 된다. 

 

현재 시점으로 1,1 두개가 담겨있으므로 2가지의 경우다.

 

 

 

 

 

이런식으로 쭉 채워주면 되는데 해당 표의 색칠은 3행을 만들때 필요한 계산이다.

 

같은 색끼리의 합이 3행에 담겨지게 되는 것이다.

 

5를 사용해서 5를 만드는 경우의 수는 1가지

 

5를 사용해서 6을 만드는 경우의 수는 6-5=1 , 1에담긴 경우의 수 1가지

 

5를 사용해서 7을 만드는 경우의 수는 7-5=2 , 2에 담긴 경우의 수 2가지

 

5를 사용해서 8을 만드는 경우의 수는 8-5=3 , 3에 담긴 경우의 수 2가지

 

5를 사용해서 9을 만드는 경우의 수는 9-5=4 , 4에 담긴 경우의 수 3가지

 

5를 사용해서 10을 만드는 경우의 수는 10-5=5 , 5에 담긴 경우의 수 4가지

 

 

이런식으로 확인해가면서 만들면 된다.

 

위에 사용했던 숫자를 계속적으로 사용하므로 동일한 부분의 결과 값을 계속 사용하는 것과 같다.

 

또한 작은 부분가지고 큰 부분의 값을 도출할 수 있으므로 DP 사용 조건에 충족한다.

 

그러므로 여태까지의 연산을 일반화시켜 DP 를 사용해서 풀면 된다.

 

 

 

이해를 돕고자 두번째 예시도 만들어봤다.

 

n=3, k=12

nums = [2, 4, 6]

 

* 빈칸은 만들 수 없다는 것을 뜻한다.

 

 

 

 

 

최종적으로 12를 만들 수 있는 경우의 수는 1 + 3 + 3 = 7 가지이다.

 

 

 

 

정답

import sys
input=sys.stdin.readline

n,k=map(int,input().split())
nums=[]
for i in range(n):
    nums.append(int(input()))

dp=[0 for i in range(k+1)]
dp[0]=1

for num in nums:
    for k in range(num, k+1):
        dp[k]+=dp[k-num]
print(dp[k])