https://www.acmicpc.net/problem/1535
https://www.acmicpc.net/problem/12865
실버2 안녕 문제와 골드5 평범한 배낭 문제이다. 입력 값 범위만 다르지 사실 상 같은 문제라 그냥 한번에 정리하면서 공부..
배낭 문제는 배낭에 최대로 담을 수 있는 무게와 각각의 무게와 가치를 가진 물건들이 주어지고 배낭에 가장 가치있게(?) 담는 방법을 묻는 문제이다. 입력 값이 충분히 작다면 단순 반복문으로도 해결되겠지만 당연히 그렇게 주지는 않을 것이다. 무시무시한 DP로 풀어야한다.
나는 DP 테이블을 만들지 못해서 다른 글들을 열심히 읽어보고 이해하는 것으로 만족했다. 나중에 또 까먹으면 들여다볼 용도로 내가 알아볼 수 있게 정리한다.
먼저 dp 테이블의 크기는 (물건 개수) * (배낭 최대 무게 + 1)로 하면 기본적인 배낭 문제는 해결이 되는 듯 하다.
문제는 이 테이블의 의미이다.
dp[ i ][ j ]의 의미는 0 ~ i번 물건을 최대 무게가 j인 배낭에 가장 가치가 크게 담기도록 했을 때의 가치이다.
- i번째 물건의 무게가 배낭의 최대 수용량인 j보다 크다면 배낭에 넣을 수 조차 없다. 그래서 dp[ i ][ j ]의 값은 dp[ i - 1 ][ j ]의 값을 그대로 쓴다. dp[ i - 1 ][ j ]는 i번째 물건을 제외한 0번째부터 i-1번째까지 물건으로 만들 수 있는 최대 가치이다.
- i번째 물건의 무게가 j보다 작다면 배낭에 넣을 수 있다. 여기서는 i번째 물건을 배낭에 담는 것이 이득인지 담지 않는 것이 이득인지 살펴봐야한다. 담지 않는다면 dp[ i - 1 ][ j ]의 값이 될 것이다. 그렇다면 물건을 담는 경우에는 어떻게 해야할까.. 나는 여기가 많이 어려웠다. 결론부터 말하자면 dp[ i - 1 ][ j - (i번째 물건의 무게) ] + (i번째 물건의 가치) 이다. dp[ i - 1 ][ j - (i번째 물건의 무게) ] 의 의미는 최대 값이 j인 가방에 0번째부터 i - 1번째 물건을 i번째 물건이 들어갈 무게를 남기고 가장 가치가 커지도록 담은 것으로 생각할 수 있다. 여기에 i번째 물건의 가치를 더한다면 i번째 물건을 포함한 상태에서 가장 가치가 크도록 배낭을 채운 것이 된다. 이제는 얘기했던대로 2가지 경우를 비교해서 더 가치가 큰 것을 dp[ i ][ j ]에 저장하면 된다.
위 과정을 통해 dp 테이블을 모두 채우고나면 테이블의 맨 오른쪽 아래 값이 정답이 된다.
먼저 S2 1535번 안녕 문제
이 문제는 배낭 무게 대신 체력으로 나와있다. 최대 체력이 100이고 100을 다 잃으면 죽어버려서 99까지만 써야된다. 무게 대신 체력, 가치 대신 기쁨으로 표현해놓았을 뿐 똑같은 문제이다.
from sys import stdin
n = int(stdin.readline())
lose = list(map(int, stdin.readline().split())) # 잃는 체력
joy = list(map(int, stdin.readline().split())) # 얻는 기쁨
dp = [[0 for i in range(100)] for j in range(n)]
for i in range(n):
for j in range(100):
if i == 0:
if lose[i] > j:
dp[i][j] = 0
else:
dp[i][j] = joy[i]
else:
if lose[i] > j:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i-1][j - lose[i]] + joy[i])
print(dp[-1][-1])G5 12865번 평범한 배낭 문제
무게의 범위가 100000으로 늘어났다. 그래도 dp로 풀면 다를게 없다.
from sys import stdin
n, k = map(int, stdin.readline().split())
items = [list(map(int, stdin.readline().split())) for i in range(n)]
dp = [[0 for i in range(k+1)] for j in range(n)]
for i in range(n):
for j in range(1, k+1):
if items[i][0] <= j:
dp[i][j] = max(dp[i-1][j-items[i][0]] + items[i][1], dp[i-1][j])
else:
dp[i][j] = dp[i-1][j]
print(dp[-1][-1])다른 문제도 몇 개 읽어봤는데 조금만 더 뭔가 더 추가되면 바로 또 머리가 지끈지끈하다. 언제쯤 dp에 적응할 수 있을지 모르겠다.
