BOJ-2293 동전 1
https://www.acmicpc.net/problem/2293
문제 소개
n가지 종류의 동전이 있다. 동전을 적당히 사용해서 그 가치의 합이 k원이 되도록 하는 경우의 수를 구한다.
각각의 동전은 몇 개라도 사용할 수 있다.
문제 풀이
dp를 사용하여 풀이하였다. 리스트 dp의 i번째 원소인 dp[i]는 가치의 합이 i원이 될 수 있는 경우의 수이다.
coin은 동전의 가치가 저장되는 리스트이다.
풀이에 앞서 아래와 같이 입력이 주어졌다고 생각해 보자.
1
2
3
4
3 10
1
2
5
이때 가치의 합이 4가 되는 경우는 아래와 같다.
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1
이를 살펴보면 1번과 2번의 경우는 가치의 합이 2가 되는 경우, 즉 dp[2] 각각의 경우에 추가적으로 2를 더하여 4를 완성시킨 것을 알 수 있다.
그리고 2번과 3번을 같이 보았을 때에는 다시 dp[3] 각각의 경우에 추가적으로 1을 더하여 4가 된 것으로 보인다.
이런 중복을 피하기 위해, 각각의 동전에 대해서 해당 동전을 추가함으로써 i가 1부터 k일 때까지 i원을 만들 수 있는 경우를 누적시켜나간다. 이를 식으로 나타내면 dp[i] += dp[i - c] 이다.
위 예시에서 1원 동전에 대한 경우의 수 누적 후 2원 동전에 대한 경우의 수를 누적한다고 가정하면, i가 4일 때 dp[4]에 더해질 dp[3]와 dp[2]는 중복되는 경우를 가지지 않는다.
dp[3]가 더해질 때에는 아직 1원 동전에 대한 경우의 수만 누적 중이므로, 2원 동전을 사용한 경우에 대한 정보가 없다. (위 예시에서 3번)
dp[2]는 2원 동전까지 사용한 경우를 누적한다. (위 예시에서 1번과 2번)
이렇게 중복을 피할 수 있으며, 어떤 동전에 대하여 먼저 누적시킬 지 순서는 상관이 없다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from sys import stdin
input = lambda: stdin.readline().rstrip()
n, k = map(int, input().split())
coin = [int(input()) for _ in range(n)]
dp = [0 for _ in range(k + 1)]
# 각 동전에 대해
for c in coin:
# i원을 만들 수 있는 경우를 누적
for i in range(1, k + 1):
# i < c 인 경우 불가능
if i < c:
continue
# i == c 인 경우 c 하나만 사용해서 가능
elif i == c:
dp[i] += 1
# i > c 인 경우 i - c를 만들 수 있는 경우에 c를 더하여 가능
else:
dp[i] += dp[i - c]
print(dp[-1])