[Python: DP] BOJ2293 - 동전1

내 머리에서 이해가 가서 행복하게 리뷰를 해본다. 호호호호

 

문제

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

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

---

입력

3 10
1
2
5

출력

10

---

1로 k를 만드는 경우

1만 사용하여 만들 수 있음! 

세로는 동전의 종류이고, 가로는 k이다. k는 입력하는 값이기 때문에 1부터 차례 차례 구해나가야 한다.

	1	2	3	4	5	6
1	1	1	1	1	1	1
2
5
결과

1로 1을 만들 수 있는 경우의 수: 1개

1로 2를 만들 수 있는 경우의 수: 1개 (1+1)

1로 3을 만들 수 있는 경우의 수: 1개 (1+1+1)

...

1로 10을 만들 수 있는 경우의 수: 1개 (1+1+1+1+...+1+1)

dp[i] = dp[i]

2로 k를 만드는 경우

1과 2를 사용하여 만들 수 있음!

	1	2	3	4	5	6
1	1	1	1	1	1	1
2	0	1	1 (3-2=1)
5	0
결과	1

2로 1을 만들 수 없음

2로 2를 만들 수 있는 경우: 1개

2로 3을 만들 수 있는 경우: 1개

 

** 집중해보자 여기서 이 문제의 핵심 DP가 나온다!

3 - 2 를 하면 1이 나온다. 2는 1개 사용된 것으로 생각하고 나머지 1을 어떻게 구할지 고려하면 된다.

여기서 1의 결과는 이미 1로 구해져있다. 이 값을 사용하여 2로 3을 만들 수 있는 경우를 구한다.

밑줄 친 부분이 DP가 사용된 곳이다. 손으로 쓰면서 계산해보면 이해가 될 것이다

	1	2	3	4	5	6
1	1	1	1	1	1	1
2	0	1	1 (3-2=1)	2 (4-2=2)	2(5-2=3)	3(6-2=4)
5	0	0	0	0
결과	1	2	2	3

예시로 2로 6을 만들 수 있는 경우의 수를 구해보자

6-2 = 4이니까 4의 결과인 3을 가져오면 해결 !

이런식으로 계속 구해주다보면 정답에 이른다.

따라서, 점화식은 dp[i] = dp[i] + dp[i-2] 이다. dp[i]는 이미 위의 표(1로 k를 구한 경우)에서 구한 결과를 가져오는 것이다. dp[i]는 계속 갱신된다.

 

5로 k를 만드는 경우

1, 2, 5를 사용하여 만들 수 있음! 앞에서 했던 것처럼 해주면 된다.

	1	2	3	4	5	6
1	1	1	1	1	1	1
2	0	1	1 (3-2=1)	2 (4-2=2)	2(5-2=3)	3(6-2=4)
5	0	0	0	0	1	1(6-5=1)
결과	1	2	2	3	4	5

5로 6을 구하는 경우의 수: 1개 (6-5=1이므로 1의 결과를 가져오면 된다)

그렇기 때문에 dp[i] = dp[i] + dp[i-5] 이다. dp[i-2]를 고려하지 않는 이유는 위에서 이미 dp[i] = dp[i] + dp[i-2]이렇게 해주었기 때문에 dp[i]에 모두 속해있는 것이다.

---

소스코드

이것을 코드로 구현하면 다음과 같다. dp[i] = dp[i] + dp[i-j]가 dp[i] = dp[i] + dp[i-2], dp[i] = dp[i] + dp[i-5]에 해당한다.

import sys
n, k = map(int, sys.stdin.readline().split())
money = []
for i in range(n):
  money.append(int(sys.stdin.readline()))

dp = [0] * (k+1)
# 1, 2, 5원 하나로 각각 1, 2, 5원을 만드는 경우의 수
dp[0] = 1

for j in money:
  for i in range(j, k+1):
    dp[i] += dp[i-j] # dp[i-i]에 해당 원(money)을 빼는 과정 
print(dp[k])

 

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

2293번: 동전 1