백준 2293번: 동전 1 (Python)

문제

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

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

입력

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

출력

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

 

 

---

 

내 풀이(틀림)

'숫자는 같지만 순서는 다른 경우를 같은 경우로 보라.'라는 조건 때문에 많고생했다. dp[i][j]를 '돈이 i만큼 있을 때, 1~j번째 동전을 이용하여 만들 수 있는 경우의 수'로 정의한 후 dynamic programming 방법으로 코딩하였다. 하지만 시간 초과가 떠버림...

 

코드

import sys

N, K = map(int, sys.stdin.readline().split())
coin_list = [0]
dp = [[0]*(N+1) for _ in range(K+1)]
for i in range(N):
    coin_list.append(int(sys.stdin.readline()))

def max_price(money, i):
    if i == 1:
        if money % coin_list[1] == 0:
            dp[money][i] = 1
            return 1
        dp[money][i] = 0
        return 0

    if money == 0:
        dp[money][i] = 1
        return 1
    
    if dp[money][i]:
        return dp[money][i]
    
    else:
        j = 0
        while(money-j*coin_list[i]>=0):
            dp[money][i] += max_price(money-j*coin_list[i], i-1)
            j += 1
        return dp[money][i]

print(max_price(K, N))

 

풀이

'ready2start'님의 풀이 링크 및 첨부 영상 참고: https://velog.io/@ready2start/Python-%EB%B0%B1%EC%A4%80-2293-%EB%8F%99%EC%A0%84-1

링크의 영상을 보고 따라하는 것이 이해하는데 가장 도움이 된다고 생각한다. 인터넷에 글로 써져있는 풀이는 뭘 봐도 잘 이해가 안 됐었는데, 내가 쓴다한들 다를까? 싶다.

dp를 1차원 배열로 선언하고, 각각의 동전마다 더하는 방식이 안 익숙하다. 이를 연습해야 할 듯.

 

코드

import sys

N, K = map(int, sys.stdin.readline().split())
coins = []
dp = [1] + [0]*K
for i in range(N):
    coins.append(int(sys.stdin.readline()))

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

print(dp[K])