[백준] - 다이나믹 프로그래밍 동전 1

동전 1

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.5 초 (추가 시간 없음)

4 MB

45880

20871

15733

45.615%

문제

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

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

입력

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

출력

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

예제 입력 1 복사

3 10
1
2
5

예제 출력 1 복사

10

---

 

모든 개수라고 하니 당연히 dfs 로 풀어야 할 것 같았다. 

다만, 문제 시간이 0.5 초라 dfs 로는 불가능할 것임을 짐작할 수 있었다. 

combination 으로 푸는 것은 개수가 10개가 넘어서 절대 불가능하고, 애초에 dfs 로 안되는 시점에서 combination은 불가능하다. 

 

dp 로만 풀 수 있다. 

문제보다 약간 더 hard case 인 k =20, coin = 2, 5, 12 인 경우이다. 

해당 문제의 알고리즘은 다음과 같다. 

 

• 다른 코인으로 k 를 몇개 만들 수 있는 가 + 현재 주어진 코인으로 k 를 만들 수 있는가? 

현재 주어진 코인으로 k 를 만들 수 있는가는 

dp[index - coin]

으로 간단하게 이전 index에서 가능했나 확인하면 된다. 

 

다른 코인으로 k 를 몇개 만들 수 있는가는 dp 의 특성인 반복해서 array를 업데이트 함으로써 확인 가능하다. 

 

위 표를 보며 아래 설명을 읽어보자. 

 

예를 들어 숫자 10은 coin 2 로 만들 수 있어서 1 이다. 

숫자 10은 coin 5로도 만들 수 있다. 

 

이에 따라 1 + 1 로 경우의 수는 2 이다. 

 

그 다음 업데이트 상황을 살펴보자. 

 

예를 들어 숫자 15는 coin 2로 만들 수 없어서 0 이다. 

하지만 15는 5로 만들 수 있다. 

 

10을 만드는 경우의 수는 아래 2개 였다. 

• 2 coin X 5 
• 5 coin X 2 

5는 이 경우의 수를 그대로 이어 받는다. 

• 2 coin X 5 + coin 5
• 5 coin X 2  + coin 5 (5 coin X 3)

즉, 다른 코인으로는 15를 바로 만들 수 없으나, 10을 이어받은 5는 만들 수 있기에 경우의 수는 2 이다. 

 

해당 문제는 위 설명의 반복으로 해결 된다. 

 

import sys 
input = sys.stdin.readline 

n,k = map(int,input().split())

coin = [0] * n

for i in range(n):
    coin[i] = int(input())

dp = [0] * (k+1)

for i in range(1,n+1):
    for j in range(coin[i-1], k+1):
        if j == coin[i-1]:
            dp[j] = dp[j-coin[i-1]] + dp[j] + 1
        else:
            dp[j] = dp[j-coin[i-1]] + dp[j]


print(dp[k])

 

코드 개선 

if j == coin[i-1]:
	dp[j] = dp[j-coin[i-1]] + dp[j] + 1

위 공식이 필요하지 않다. 

 

간단하게 

dp[0] = 1

처리하면 된다. 

 

즉, dp[0] 은 항상 dp 를 만들어나갈 때 초석이 되는 element 로 활용된다는 것을 기억하면 앞으로 문제에서 이번같이 비효율적으로 코드를 작성할 일이 없어진다.