[BOJ] 2293 동전 1

date

Aug 7, 2023

slug

boj-2293

author

status

Public

문제 링크

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

문제

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

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

문제풀이

도저히 모르곘어서 답을 통해 해결했다.

https://mong9data.tistory.com/68

위 글에서는 다음과 같이 해결한다

‘가치의 합이 k원인 경우의 수를’ 보다 낮은 i가 되는 경우의수를 구하는 부분 문제로 나누었고

특정 동전을 사용했을때 가치의 합이 i원이 되는 경우의 수를 구하는 문제로 바꾸어 해결하였다.

합이 i원이 되는 경우의수를 구하기 위해 dp배열을 만들고, dp[a]는 합이 a원이 되는 경우의 수를 구한 것이다. 이떄 dp[0]에 대한 처리도 따로 해주어야하는데

합이 0이 될 수는 없으므로 1로 처리한다.

코인의 종류에 따라 순회한다.

이때 코인의 값과 코인의 값부터 시작해서 k까지 순회하는 코드를 추가하여

for coin , 1~coins, for i , coin~k로 하여

i-coin 가 0일경우는 코인이 딱 한개만 쓰이는 경우, dp[0]은 1로 한다.

i-coin 가 0보다 클 경우는 i-coin 의 값이 지금 사용하는 코인을 제외한 그 전의 코인까지의 합 dp[i]에 지금 코인을 사용한 값 dp[i-coin]을 더하여 저장하면 된다.

파이썬 문제풀이 코드


import sys
input = sys.stdin.readline

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

coins = []
dp = [0 for i in range(k+1)]
dp[0] = 1 # 동전을 한개만 사용하는 경우


for _ in range(n):
    num = int(input())
    coins.append(num)


for coin in coins:
    for i in range(coin, k+1):
        if i-coin >= 0: # 동전을 사용할 수 있는 경우
            dp[i] += dp[i-coin] 
            
print(dp[k])

시간복잡도

O(nK) ≤ 0.5s , ≤ 4MB

입력

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

출력

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

예제 입력

예제 출력

알고리즘 분류

구현

문자열