[DP] 동전 1 - 백준

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

2293번: 동전 1

 

DP 유형의 정석과도 같은 문제이다.

아예 이 문제를 암기해도 괜찮을거 같다.

 

참고 포스팅 : 

https://www.youtube.com/watch?v=2IkdAk1Loek

https://velog.io/@ready2start/Python-%EB%B0%B1%EC%A4%80-2293-%EB%8F%99%EC%A0%84-1

 

이 문제는 쉽게 말하면 부분 문제로 전체 문제를 푸는 아이디어에 기초한다.

 

예를 들어보자

2, 5, 7 조합으로 11을 만들어야 한다고 해보자

이 문제는 이런 느낌이다

저 조합으로 만약에 9를 조합해야 한다고 해보자

우선 현재 우리는 2, 5를 사용하여 조합을 진행 중이다.

2와 5만 사용하여 9는

2를 2번, 5를 1번 사용하여 9를 조합할 수 있다.

그리고 이제 7이라는 새로운 동전을 가지고 조합을 해보자

7이라는 녀석을 사용하려고 하면 9 - 7 = '2'라고 하는 차이가 남는다

만약에 이 2라는 녀석을 만들 수 있는 경우의 수가 있으면 그 경우의 수 만큼 경우의 수가 추가 된다.

즉, f(9) 라는 녀석은 7을 새로 썼을 때,

f(9) = f(9) + f(9-7) 이라고 하는 녀석이 추가되는 것이고

f(2)는 이미 이전에 계산된 녀석이면

그 녀석을 가지고 와서 추가하면 된다

 

 

이 논리는 다음 논리에 기초한다.

우선 다음 표를 생각해보자

여기서 unit을 해당 row의 가장 작은 coin만 활용하여 구성할 수 있는 지를 먼저 봐보자

여기서는 2에 해당한다

그럼 다음과 같이 row가 구성됨을 알 수 있다.

나누어서 나머지가 0이 되지 않는 것은 해당 coin으로만 사용해서는 해당 unit을 구성할 수 없음을 의미한다.

밑의 sum은 현재까지 사용한 동전으로 해당 unit을 구성하는 경우의 수의 총 합을 의미한다.

 

다음은 5를 보자

5를 사용할 경우에는 5보다 작은 수는 당연히 구성할 수 없으므로 0이 되고

5같은 경우는 1번 사용하면 되므로 1을 추가해준다 그 뒤로 sum도 갱신해주게 된다.

 

다음 6을 구성하는 경우를 보자

6의 경우 5만 가지고는 구성이 되지 않지만

여기서 중요한 점은 5를 사용하고 나서 나머지의 값의 경우의 수가 존재하는 지를 체크해주어야 한다!

예를 들어 여기서 6의 경우 5를 하나 사용하면 1이 남는데

1을 구성하는 경우의 수가 0이므로 0을 이제껏 누적되었던 6의 경우의 수에 더해주면 된다

따라서 sum[6] 은 1+ 0 = 1이 된다

이러한 논리로 구축을 해주게 된다

 

단위가 되는 2부터 오름차순으로 조합을 살펴보았고

구성된 코드는 다음과 같다.

 

n, k = [int(x) for x in input().split()]
coin = [ int(input()) for x in range(n) ]
sum_dict = {}

mini = min(coin) ## 단위
## 초기 sum값 setting
for i in range(k+1) :
    sum_dict[i] = 0

for co in sorted(coin) :
		## 단위로 초기 경우의 수 값 setting
    if co == mini :
        for i in range(co, k+1) :
            if i%co == 0 : sum_dict[i] += 1
    else :
        for i in range(co, k+1) :
						## 자기 자신인 경우
            if i == co :
                sum_dict[i] += 1
						## DP 논리 적용
            else :
                sum_dict[i] += sum_dict[i-co]
print(sum_dict[k])