[백준] 2293 동전 1

※ 사용언어 : 파이썬 ※

 

▼ 문제 링크 ▼

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

2293번: 동전 1

 

---

 

문제 접근

1) K이 동전으로 만들어야하는 가치의 합이면, 이번 문제의 점화식은 dp[K]+=dp[K-동전의 액수] 이다. 어떤 방식으로 이런 점화식이 탄생하게 되었는지 천천히 알아보도록 하겠다.

 

예시) 동전의 종류=[1원, 2원, 3원]이고 가치의 합 K=5 인 경우

K를 1부터 5까지 하나씩 증가시키며, 가지고있는 동전을 점진적으로 늘려가며(처음에는 1원만, 그 이후에는 2원 1원, 그 다음에는 3원, 2원, 1원) 가치의 합이 K가 나오는 경우를 구한다.

여기서 한가지 규칙을 찾을 수 있다. 

(초록 표 안에 숫자에서 단위인 원은 생략했다.)

바로 2원을 사용하는 경우에서 해당 규칙을 찾을 수 있다.

K=4에서 k=2에서 쓰인 경우가 보인다는 점이다. (빨간 박스)

이 부분을 점화식으로 만들어보면 dp[4] += dp[4-2=2] 가 나오게 된다.

그렇다면 K값이나 동전의 종류가 다를 때도 이런 식의 결과가 나오는지 조금 더 알아보겠다. 

K를 6까지 늘리고(K=1인 경우는 표에서 생략했다.) 3원의 동전을 쓰는 경우

K=6에서 K=3에서 보인 경우가 나타난 것을 볼 수 있다. (보라색 부분)

이 부분을 점화식으로 표현하면 dp[6] += dp [6-3=3] 이라는 걸 알 수 있다.

그렇다면 K=6에서 2원을 사용한 경우 K=6-2=4에서 2원을 통해 만든 경우의 수가 발견되어야 한다.

실제로 위에 이미지의 주황색 영역으로 표시된 부분을 보면 k=4에서 보여진 경우가 k=6에서도 보여지는 것을 확인할 수 있다.

 

---

 

문제풀이(With Python) 

import sys

N,K=map(int,sys.stdin.readline().split())

coin_list=[]

for i in range(N):
    coin_list.append(int(sys.stdin.readline()))

dp=[0 for _ in range(K+1)]
dp[0]=1
for coin in coin_list:
    for i in range(coin,K+1):
        dp[i]+=dp[i-coin]

print(dp[K])

◇ dp의 크기가 K+1인 이유는 K까지 구해야하기 때문이다. dp의 크기를 K로 설정하게 되면 dp는 0~K-1까지 생성되게 된다. 그렇게 되면 K값일때 경우의 수를 저장할 공간이 없게 된다.

◇ dp[0]을 1로 초기화 시켜준 이유는 다음과 같다. 만약 dp[i]+dp[i-coin]에서 i가 2이고, coin이 2원인 경우, dp[i-coin]은 dp[0]이 된다. 이때 dp[0]값이 이면, dp[2] 자체가 0이 된다. (dp[2]+=dp[0]) 그러나 2원짜리 동전으로 2원을 만드는 경우의 수는 1개가 존재하기 때문에 dp[0] 자체를 1로 초기화해서 코인 가격과 K가 같을 경우의 수를 만들어준다.

(coin이 2원이고 K의 값도 2원이면 나올 수 있는 경우의 수는 2원을 내는 1가지 경우 뿐이다.)