(Python/🥇5)백준알고리즘 2293번: 동전 1

 

문제 바로가기 

동전1

문제:

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

입력:

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

 

출력:

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

 

풀이 :

 

첫 번째 시도

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n,k = map(int,sys.stdin.readline().split(" "))

lst = sorted([int(sys.stdin.readline().rstrip()) for i in range(n)])
dp = [0] * (k+1)
dp[0] = 1
for i in lst:
    dp[i] += 1

for i in range(1,k+1):
    for j in lst:
        if j < i:
            dp[i] = max(dp[j]+1, dp[i-j]+dp[j])
print(dp[-1])

첫 번째 시도는 그냥 완전히 잘 못 알고 있었다 애초에dp[j] + 1 이 말도 안되는것이다.

근데 dp[i-j] +dp[j] 는 맞지만 최댓값으로 바꾸는게 아니라 계속 더해줘야하는 것이다.

 

두 번째 시도

 

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n,k = map(int,sys.stdin.readline().split(" "))

lst = sorted([int(sys.stdin.readline().rstrip()) for i in range(n)])
dp = [0] * (k+1)
dp[0] = 1

for coin in lst:
    for i in range(coin, k + 1):
        dp[i] += dp[i - coin]

print(dp[k])

 

그것을 수정하면 이렇게 된다.

 

lst를 돌면서 코인을 뽑고 k까지 채워주면 된다.

그리디 알고리즘도 쓰는것 같다.

 

dp[i]는 가치의 합이 i원이 되도록 하는 경우의 수를 저장한다.
이전 단계에서 이미 계산된 경우의 수가 저장되어 있고, 새로운 동전을 추가하면서 경우의 수를 누적해 나간다..

예를 들어, 동전의 가치가 2원이고 i가 5라고 가정해보자.
그러면 5원을 만들기 위해서는 동전 2원과 3원을 사용하는 방법이 있다.
즉, dp[5]는 dp[3]과 dp[5-2]의 합과 같다. 
따라서 dp[5] += dp[5 - 2]가 된다.


만약 코인이 2,5 이고 k가 10이면
2는 2 코인으로 만들수 있다 >> i-coin = 0  dp[0] = 1이므로 1로 바뀌고
그 뒤로 쭊쭉 간다
3은 2와,5로는 못 만든다. 즉 3-2 = 1 dp[1] = 0 이므로 0 이되고
4 는 4-2 = 2 dp[2] = dp[1]+1 
5 는 5-2 = 3 은 없어서 못 만든다.

 

빅오 : O(nk)

동전의 개수 n에 비례