배낭문제

백준 동전문제 9084

정답코드

# 동전
T = int(input())
for _ in range(T):
  N = int(input())
  coins = list(map(int,input().split()))
  money = int(input())
  cnt_lst = [0]*(money+1)
  cnt_lst[0] = 1
  for coin in coins:
    for bill in range(coin,money+1):
      cnt_lst[bill] += cnt_lst[bill-coin]
  print(cnt_lst[-1])

이전에 풀이한 가장 기본적인 배낭문제

중복 없고 최대 가치를 배낭에 담기

n, k = map(int,input().split())
graph = [list([0]*(k+1)) for _ in range(n+1)]
for i in range(1,n+1):
  w, v = map(int,input().split())
  for j in range(1,k+1):
    if j < w:
      graph[i][j] = graph[i-1][j]
    elif j >= w:
      graph[i][j] = max(graph[i-1][j-w] + v, graph[i-1][j])
print(graph[n][k])

가장 기본적인 배낭문제는 현재의 무게와 가치가 주어졌을 때 이 전에 가방에 이미 현재 무게가 포함된 경우(이전 값 그대로 가져오기),
포함되지 않은 경우(현재 무게를 뺀 이전 최대 가치에서 현재 가치 더한 값)로 나누어서 둘 중에 가치가 큰 값을 저장한다.

이번에 풀이한 동전 문제는 조금 다르다.
일단 동전이라 중복이 허용되고 가치가 아니라 전체 경우의 수를 저장해나가야 한다.
이전 경우의 수에 현재 새로 추가된 n-coin의 경우의 수를 더해야 한다.

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

0 길이를 1로 초기화 한 이유는 1원이 1원일 경우에 경우의 수는 1개로 시작하므로,
본인 동전의 크기 보다 작은 이전의 크기에서는 그냥 위에 경우의 수를 그대로 내려서 가져오면 된다.
크기가 본인 동전 크기 이상이면 이전에 해당 크기의 경우의 수(위의 값)에 현재 크기에서 동전의 크기만큼 뺀 값의 최신 경우의 수를 더해주면 전체 경우의 수가 업데이트 된다.

이런 중복이 허용된 경우의 배낭 문제는 보통 배열을 2차원 말고 1차원으로 생성하면 더 간단해진다. 어차피 최신 값이면서 현재보다 coin 만큼 작은 값은 현재 행의 앞에 있고 이전 경우의 수는 위의 행에 있지만 1차원 배열로 생성하면 현재 최신화 이전의 자기 자신의 위치 값이다.