알고리즘 유형 : DP(Dynamic Programming), 냅색
풀이 참고 없이 스스로 풀었나요? : X
https://www.acmicpc.net/problem/2293
소스 코드(파이썬)
import sys
input = sys.stdin.readline
n, k = [*map(int, input().split())]
coins = [int(input()) for _ in range(n)]
# column = 5 이고 row에 해당하는 coin = 5 인 경우, column-coin 조회할 때 인덱스가 0인데,
# 이 때 빼주는 것 자체가, 5짜리 coin 한 번 사용한 상태이기 때문에, 설령 column = 0이어도
# 경우의 수 하나를 더 해줘야하므로, column = 0 에는 1을 채워준다.
# 0원은 아무 코인도 안 쓰면 되니 경우의 수가 하나다! 라고 생각해도 될듯.
knapsack = [1] + [0]*k
for coin in coins:
# coin 값 열 인덱스부터 for를 돌아준다.
# 그 이전의 인덱스는 어차피 현재 코인을 못 쓰므로,
# 원래 그 인덱스에 있던 값(이전 코인들에 대한 경우의 수)
# 을 그대로 두면 된다. 그게 곧 현재 코인을 0개 사용하며
# 그 이전의 코인을 활용한 경우의 수이다.
for col in range(coin, k+1):
knapsack[col] += knapsack[col - coin]
print(knapsack[k])풀이 요약
- 이 문제는 냅색 알고리즘으로 풀 되, 점화식을 세워본 뒤 자세히 살펴보면
메모이제이션 배열을 1차원으로 구성해도 알맞게 구현을 할 수 있다는 것을 알 수 있고, 이를 활용해 메모리 사용을 최소화해야한다.
- 우선 메모이제이션 1차원, 메모리 최소화 이런건 잠시 제쳐두고, 냅색 알고리즘을 먼저 적용해보자.
-
동전은 여러 개 주어지는데, 이 동전들은 몇 개는 아예 안 써도 되고, 전부 다 써도 된다. 냅색 알고리즘의 행에 해당하는 조건이다. 즉 이 것을 메모이제이션 배열의 행으로 둔다.
이제 점화식을 대충 생각해보자.
설명의 편의를 위해 미리 완성된 메모이제이션 배열을 보여주고 설명하겠다.
행:코인
열:목표 가치 합0 1 2 3 4 5 6 7 8 9 10 - 1 0 0 0 0 0 0 0 0 0 0 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
세 번째 코인(행) 가치 합 10 경우의 수는, 해당 코인(5)를 쓰느냐 안 쓰느냐로 나눌 수 있다. 경우의 수이므로 두 경우를 모두 더해줘야한다.
1) 해당 코인(5)을 안 쓰는 경우, 그 이전 행의 값(1, 2코인을 쓰는 경우의 수)이 현재 경우의 수이다.
2) 해당 코인(5)를 쓰는 경우, 5코인 하나는 반드시 포함을 시켜야하므로, 일단 5코인 한 개를 써보자. 그러면, 10에서 5를 빼고, 나머지 가치 5를 1, 2, 5코인 3개로 채워야한다. 즉 같은 행의 (현재열10-coin값5)=5열의 값이 현재 경우의 수이다.
이제 1), 2) 경우의 수를 더해주면 그게 세 번쨰 코인(행) 가치 합 10 경우의 수이다.
한 가지 주의할 것이 있다. 만약 세 번째 코인(5) 행 가치 합 5에 해당하는 열의 값을 구할 때, 열 5에서 코인 값 5를 빼면 0이다. 그런데 코인 값 5를 뺐다는 것 자체가 5코인 하나를 사용했다는 것으로 이는 경우의 수 하나로 카운팅해줘야한다. 즉 모든 행의 0열, 즉 가치 합 0은 경우의 수를 모두 1로 초기화해준다. 달리 생각하면 가치 합 0은 그냥 모든 코인을 안쓰면 되므로 경우의 수가 1인 것이다.
knapsack[row][col] = knapsack[row-1][col] + knapsack[row][col-coin값](if col >= coin값)이 때 점화식에서 row-1을 조회하므로, 코인의 개수 3개에서, 행을 하나 더 만들어서 총 4개의 행으로 만들자, 코인 1개에 해당하는 2번째 행을 채울 때, 0열만 1이고 나머지가 0인 1번째 행을 조회한다.
- 그런데 문제에서 제한하고 있는 메모리는 4MB(=400만 바이트)이다. 메모이제이션 배열의 최대 크기는 101*10001 = 약 100만. 한 칸에 정수형 4바이트가 들어가므로 약 400만 바이트이고, 여기에 입출력을 받는 코인들 리스트까지 생각하면 400만 바이트를 넘게 된다. 즉, 메모이제이션 배열의 크기를 줄일 방법을 강구해야 한다.
-
이제 점화식을 다시 살펴보자.
knapsack[row][col] = knapsack[row-1][col] + knapsack[row][col-coin값](if col >= coin값)어떤 (행,열)의 값이든, 반드시 그 이전 행의 값을 더해준다는 것을 볼 수 있다. 그리고 메모이제이션 배열을 채울 때, for문을 돌면서 0행부터 순서대로 채워나간다. 각 행에 대해 열도 마찬가지로 맨 왼쪽에서부터 채워나간다(index가 작은 것부터 큰 쪽으로)
이 것이 의미하는 것이 있다. 어차피 이전 행의 값을 더해주니까, 굳이 다음 행으로 넘어가는 작업을 하지말고, 다음 행을 구하기 위해서 그냥 현재 행에다가 knapsack[row][col-coin값]를 더해주면 결과적으로 다음 행의 값을 구해준 셈이 된다.
게다가, knapsack[row][col-coin값] 같은 경우에도, 0열부터 쭉 채워나가기 때문에, 현재 위치인 col에서, coin값을 뺀 열 값을 조회하는데, 이는 현재 위치의 열인 col보다 반드시 작거나 같으므로, 채우는 순서에 의해 knapsack[row][col-coin값]은 이미 다음 행의 값이 이미 구해져있는 상태이므로, 다음 행까지의 코인을 활용한 경우의 수를 조회하여 더해준 셈이 되는 것이다.
이러한 이유로, 메모이제이션 배열은 1차원으로도 충분하며, 기존의 행을 거듭하며 채워나가던 작업을, 1차원 배열을 0열부터 마지막 열까지 덧씌워나가는 작업을 반복하는 것으로 대체한다.
그리고 배열의 초기값은, 기존의 0행과 같이, 가치 합 0(0열)만 1로 두고 나머지는 다 0으로 둔다. 이 후 코인 1개, 코인 2개, ...에 대해 덧씌워주는 작업을 수행하면 된다.
- 구현은 아주 쉽다. 위에서 설명한 대로 1차원 배열을 할당하고, 초기화를 해주고, coin을 돌면서, column index를 coin값부터 돌면서(그 이전 값은 어차피 coin을 못쓰니까) knapsack[col - coin]을 더해주면 된다.
배운 점, 어려웠던 점
- 냅색 알고리즘으로 푸는 시도는 했는데, 정말 당연한 사실이지만 메모이제이션 배열의 원소가 경우의 수여야하는데 다른 짓을 열심히 해버렸고, 그러다보니 당연히 점화식도 생각해내지 못했다. 결국 다른사람 풀이를 참고했다.
- 냅색 알고리즘을 적용하는 프로세스, 그리고 어떤 때에 쓸 수 있는지에 대한 경험을 쌓을 수 있었다.
- 점화식의 형태에 따라, 메모이제이션 배열의 형태를 바꾸는 등 응용 경험을 할 수 있었다.
