백준 2293 : 동전 1

배낭 문제와 비슷한 원리로 풀리는 문제인데,

처음에 아이디어를 잘못 가져다가 고민을 하는 바람에 시간이 엄청 걸렸다.

한 번에 안 풀려서 방치하고 있다가 푸는데 거의 이틀이 걸렸다...

 

핵심 아이디어 :  내가 현재 몇 종류의 동전을 가지고 있다면, 그 때 그 동전들을 가지고 목표값을 만들 수 있는 모든 경우의 수를 저장하는 것

 

처음에 나는 dp에 경우의 수를 저장하지 않고 각 동전이 입력될 때 그것을 가지고 만들 수 있는 누적합 비슷하게 저장하려고 시도했었다.

그러기 위해서 dp 를 2차원 배열로 만들고 온갖 헛수고를 했는데,

다시 생각해보면 문제풀이를 시작한 극초반에 다양한 아이디어가 스쳐가던 중 배낭 알고리즘 활용하는 방법이 뇌리에 스쳤었는데 그것을 구체화하지 못했던 것이 아쉽게 느껴진다.

 

난 항상 느끼지만 문제를 오래 보다 보면 뭔가 생각이 경직이 되서 다양한 생각이 안나오는 것 같다...

 

반성문 비슷하게 상관없는 얘기들이 길었는데, 본격적인 문제 풀이를 하기 전에 배낭 알고리즘에 대한 아이디어를 먼저 소개하고 이 문제를 2차원 배열로 푸는 경우, 1차원 배열로 푸는 경우 순으로 글을 진행하려 한다.

---

내가 예전에 풀었던 배낭 문제 풀이

백준 12865 : 평범한 배낭 (파이썬)

---

이 글에서도 다시 한 번 짚고 넘어가자면 배낭 문제는...

각자 다른 가치를 가지는 물건들이 많이 있고 내가 들 수 있는 무게는 제한되어있는 와중에,

모든 물건들의 조합을 비교해가며 무게 한도를 넘지 않는 선에서 가장 가치가 높은 조합을 구하기 였다.

 

이것을 푸는 방법은 위의 포스트에서 설명하고 있지만 간략히 설명하면,

아무 변화가 없는 현재 상태와, 현재 상태에서 지금 넣으려는 무게를 또 넣은 것을 비교해서 그 때 서로 더 가치가 큰 경우를 dp에 저장하는 것이었다.

 

동전 1 문제도 비슷하게 풀 수 있다.

저 위에 쓰여 있는 말을 동전 1 문제에 맞게 가공해서 다시 본다면...

각자 다른 가치를 가지는 동전들이 n 종류 있고 내가 만들 수 있는 총액은 k 로 제한되어있는 와중에,

모든 동전들의 조합을 비교해가며 총액 k 를 넘지 않는 선에서 가장 가치가 높은 조합을 구하기 이다.

 

주어진 동전들을 빠짐없이 모두 사용해야 하기 때문에 총액 k 를 넘지 않는 선에서 가치가 큰 동전들을 넣을 수 있는 경우는 빼먹지 않고 넣어줘야 한다.

 

우선 단순하게 계산해보면서 표 dp를 완성시켜보면 이렇다.

(한글로 만든 표 그냥 붙여넣기 하면 되는게 신기하다...)

 

	0	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1	1
2	1	1	2	2	3	3	4	4	5	5	6
5	1	1	2	2	3	4	5	6	7	8	10

 

표를 보면서 이해하면 쉽게 이해할 수 있다.

 

1원만 가지고 있을때 :

 

0원 : 동전을 사용하지 않는 경우 한 가지
1원 : 1원 짜리 한 번 사용 => 1
2원 : 1원 짜리 두 번 사용 => 1
...
10원 : 1원 짜리 열 번 사용 => 1

 

1원과 2원을 가지고 있을때 :

 

0원 : 모든 동전을 사용하지 않는 경우 한 가지
1원 : 1원 짜리 한 번 사용 => 1
2원 : 1원 짜리 두 번 사용 / 2원 짜리 한 번 사용 => 2
...
10원 : 1원 짜리 열 번 사용 / 2원 짜리 ... => 6

 

이런 식으로 진행이 되면서 표가 그려지는데,

표에서 dp[i][j] 는 i 원 까지의 동전들을 가지고 있을 때 그것들로 j 원을 만들 수 있는 모든 경우의 수 임을 알 수 있다.

 

우리는 일일히 손으로 세지 않고도 dp의 어떤 패턴을 통해 저 표를 완성하는 방법을 알고 싶다!

배낭 문제에 대한 사전 지식이 없는 사람이라면 약간 헤맸을 수도 있다.

 

표를 다시 한번 보자.

 

	0	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1	1
2	1	1	2	2	3	3	4	4	5	5	6
5	1	1	2	2	3	4	5	6	7	8	10

 

가령 현재 5원 동전까지 있는 상태이고 만들 수 있는(만드려는) 총액이 5원이라고 했을 때,

식은 아래와 같이 된다.

1원과 2원으로 5원을 만드는 경우 +
5원만 사용해서 만드는 경우
= dp[5][5]

1. 1원과 2원으로 5원을 만드는 경우는 표를 보면 dp[2][5] 에 저장되어 있음을 금방 알 수 있다.
2. 그럼 5원만 사용해서 만드는 경우는?
   
   • 총액에서 먼저 5원을 집어 넣으면 나머지 채워야 할 액수가 0원이다.
     • 이 때는 더 이상 할 것이 없다. => 5원만 넣으면 된다. => 한 가지 경우 이다.
     • 기존에 1원과 2원으로 5원을 만드는 경우는 세 가지였다.
     • 둘을 합하면 만들 수 있는 경우는 모두 네 가지 이다.
   • 즉 전체 j 에서 가장 액수가 큰 동전부터 채워 넣어가며 나머지 채워야 할 양 만큼 다시 계산하는 것이다.

 

이번에는 7원을 만드는 경우를 보자.

 

1원 짜리와 2원 짜리 가지고 총액 7원을 만들 수 있는 네 가지 경우를 기초로(dp[2][7]), 채워야 할 총액 7원에서 5원을 넣었을 때 나머지인 2원을(dp[5][2]) 1원 짜리와 2원 짜리로 채우는 경우의 수를 더한 것이다.

 

배낭 문제와 비슷한 풀이로 풀린다는 이유가 바로 이러한 흐름으로 문제풀이가 진행되기 때문이다.각 가능한 경우의 수를 칸에 저장해 두었다가 필요할 때 저장하는 것이다.

 

이제 노가다로 풀지 않고 앞선 원리로 다시 표를 채워보자.(편의상 1원 부분은 생략)

---

	0	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1	1
2	1	1	2	2	3	3	4	4	5	5	6
5

 

1원과 2원을 가지고 있을때 :

0원 : 1원만 쓸 수 있으므로 1원의 경우에서 그대로 내려온다.

1원 : 1원만 쓸 수 있으므로 1원의 경우에서 그대로 내려온다.

2원 : 2원 짜리 하나를 먼저 넣으면 이제 채워넣어야 하는 액수는 0원이 남고, 남은 동전들로 0원을 만들 수 있는 경우는 모두 쓰지 않는 한 가지 이다.

(위에 같이 얘기하면 좀 비 직관적이긴 한데, 이해하기 쉽게 얘기하면 기존에 있던 1원으로 2원을 만드는 경우의 수 (한 가지) 에다가, 만들어야할 총액 2원에 2원을 넣고 남은 양이 0원이 되면 더 이상 할 게 없기 때문에 오직 2원에 2원을 넣은 경우 단 한가지 경우만 추가하는 것 이라고 이해했다)

3원 : 2원 짜리 하나를 먼저 넣으면 1원이 남고, 남은 동전들로 1원을 만들 수 있는 경우는 한 가지 이다.

...

10원 : 2원 짜리 하나를 먼저 넣으면 8원이 남고, 남은 동전들로 8원을 만들 수 있는 경우는...

• 2원 짜리 하나를 먼저 넣으면 6원이 남고, 남은 동전들로 6원을 만들 수 있는 경우는...
• 2원 짜리 하나를 먼저 넣으면 4원이 남고...

같은 패턴이 반복된다.

---

이로써 우리는 필요한 핵심 코드를 만들 수 있게 되었다.

 

for _ in range(동전의 개수):
    어떤 동전 = int(sys.stdin.readline())
    for 현재의 목표 액수 in range(1, 목표 액수 + 1):
        if 현재의 목표 액수 >= 어떤 동전:
            dp[현재의 목표 액수] = dp[현재의 목표 액수] + dp[현재의 목표 액수 - 어떤 동전]
        # == dp[현재의 목표 액수] = dp[기존의 목표 액수] + dp[현재의 목표 액수 - 어떤 동전의 가치]

 

아래는 전체 코드이다.

 

import sys
n, k = map(int, sys.stdin.readline().split())
dp = [0] * (k + 1)
dp[0] = 1
for _ in range(n):
    v = int(sys.stdin.readline())
    for t in range(1, k + 1):
        if t >= v:
            dp[t] += dp[t - v]
print(dp[-1])

---

처음에 리스트를 2차원으로 만들어서 풀려는 시도를 했는데 다시 생각해보니 굳이 2차원으로 만들 필요가 없었다.

왜냐하면 이번에 어떤 동전이 들어왔다면, 기존 dp값에 이번에 들어온 동전으로 만들 수 있는 경우를 누적시켜주면 되기 때문이다.