💡 백준 12865:
주어진 물건들을 순회하며 해당 물건을 넣는 경우와 빼고 가는 경우의 가치 총합을 계산하여 최댓값 출력
🌱 코드 in Python
알고리즘: Dynamic Programing
이번 문제는 내겐 아직 너무 먼 그대였기 때문에 ^^;;;
몇시간 고민하다가 결국 답지를 찾아 헤매게 되었는데, 그 마저도 첨엔 이해가 잘 안돼서 힘들었다 ㅎ
그래서 이왕 찾는김에 여러 방법을 찾아보게 되었다
(모든 예는 백분 문제의 예제 입력과 동일)
🕶 첫번째 방법: 2차원 dp 배열 활용
import sys
n, k = map(int, sys.stdin.readline().split())
dp = [[0] * (k + 1) for i in range(n + 1)] # 각 아이템 갯수 * 무게 2차원 dp배열 생성
for i in range(n): # 물건 n개 만큼 탐색
w, v = map(int, sys.stdin.readline().split()) # 각 물건의 무게와 가치 입력 받기
for j in range(1, k + 1): # 각 물건마다 1 ~ k까지의 무게의 경우 확인
if j >= w: # 탐색 무게가 입력받은 무게와 같거나 무게보다 큰 경우
if dp[i][j - w] + v > dp[i][j]: # 탐색 무게 - 현재 물건의 무게를 뺀 경우의 가치 + 현재 물건의 가치가 현재 탐색 무게의 가치보다 큰 경우
dp[i + 1][j] = dp[i][j - w] + v # 탐색 무게 - 현재 물건의 무게를 뺀 경우의 가치 + 현재 물건의 가치로 현재 물건의 탐색 무게 가치 갱신
else: # 현재 탐색 무게의 가치가 더 큰 경우
dp[i + 1][j] = dp[i][j] # 기존 가치 유지
else: # 탐색 무게가 입력받은 무게보다 작은 경우
dp[i + 1][j] = dp[i][j] 기존 가치 유지
print(dp[n][k])2차원 배열로 구현할 경우 각 물건에 대하여 자신을 넣을 수 있는 모든 무게의 경우에 대하여 값을 비교하여 갱신하게 된다
자신보다 작은 무게의 경우는 해당 물건을 넣는 경우의 수는 고려할 수 없으므로 기존 물건들로 갱신된 가치를 그대로 유지한다
문제의 가방에는 7kg까지 넣을 수 있으므로 1~7kg을 채우는 경우의 수를 탐색하여 최댓값을 찾아야 하는데,
세번째 물건부터 볼 경우 3kg이므로 1~2kg는 해당 물건을 넣을 수 없기 때문에 고려하지 않고 기존 가치를 그대로 유지한다
이후 3kg부터 가치 비교를 시작하는 데 dp[2(=2번째 물건까지 탐색한 결과가 저장된 배열][0(3-3)] + 6(3번째 물건의 가치)의 값과
dp[2][3]을 비교하여 큰 값을 dp[3(=3번째 물건까지 탐색한 결과가 저장된 배열][3]에 저장한다
그 전 물건까지 3kg짜리 물건이 없었기 때문에 dp[2][3]은 0이었을 것이고, dp[2][0]도 0이기 때문에 전자의 가치가 저장되게 된다
dp[2][4] ~ dp[2][6]까지는 3kg물건과 같이 넣을 수 있는 물건이 없으므로 계속 3kg 가치로 값이 갱신되다가
j가 7이 되는 순간 dp[2][4(7 - 3)] = 8 + 6 = 14로 값이 갱신된다
이런 식으로 j >= w(j range(k + 1))는 해당 물건을 넣을 수 있는지 확인하고,
dp[i][j - w] + v > dp[i][j]를 통해 해당 물건을 넣는 것이 이득인지, 아니면 빼는 것이 이득인지 확인할 수 있다
이 코드의 경우 각 아이템 별로 들어갈 수 있는 kg의 경우의 수를 모두 파악해야 하므로 시간이 조금 오래걸리는 편이다
🕶 두번째 방법: 1차원 dp 배열 활용
import sys
n, k = map(int, sys.stdin.readline().split())
ret = [0] * (k + 1)
for i in range(n):
w, v = map(int, sys.stdin.readline().split())
if w > k: # 최대 무게보다 큰 경우 고려하지 않음
continue
for j in range(k, 0, -1): # 무거운 무게부터 탐색
if w + j <= k and ret[j] != 0: # 현재 물건의 무게 + 탐색 무게가 최대 무게보다 작거나 같고, ret[j] = 해당 무게 가치가 갱신되어 있는 경우
ret[w + j] = max(ret[w + j], ret[j] + v) # 현재 물건의 무게 + 탐색 무게의 가치 갱신
ret[w] = max(ret[w], v) # 현재 물건의 가치와 현재 물건의 무게에 갱신되어 있는 가치 비교
print(ret[k])1차원 배열로 구현한 경우 기본적인 논리구조는 2차원 배열과 비슷하다고 볼 수 있다
다만 다른 부분은 w + j <= k and ret[j] != 0 이 조건식에서 ret[j] != 0 부분으로 갱신된 경우(=해당 무게를 다른 조합으로 만들었거나,
단일 물건으로 채울 수 있었던 경우)에만 갱신 경우를 탐색하는 것이다
(근데 생각해보니 이부분도 2차원 배열에 넣을 수 있을 것 같기두..)
아무튼 이것도 현재 물건을 가방에 넣을 수 있는 경우에 넣는 경우와 빼는 경우를 고려하여 가치를 갱신하는 것이다
🕶 세번째 방법: 딕셔너리 자료형 활용
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
k += 1
items = [tuple(map(int, input().split())) for _ in range(n)]
items.sort(reverse=True) # 무거운 물건부터 탐색하도록
dp = {0 : 0}
for w, v in items: # 각 물건을 돌면서 순회
tmp = {}
for dp_v, dp_w in dp.items(): # 각 물건에 대해 dp 딕셔너리 전체를 순회하며 탐색
if dp.get(nv:= dp_v + v, k) > (nw := dp_w + w): # dp 가치 + 현재 가치가 dp배열 안에 있을 경우 해당 무게, 없을 경우 기본값으로 최대 무게 + 1을 해둔 k와 dp무게 + 현재 무게보다 클 때
tmp[nv] = nw # 새 가치는 새 무게
dp.update(tmp) # dp배열 갱신
print(max(dp.keys()))딕셔너리 자료형의 경우 key값에 대한 value가 수정될 수 있다
또한 해당 key가 배열 안에 없을 경우 기본 값을 반환할 수 있어
dp.get(nv: dp_v + v, k) > (nw := dp_w + w) 조건에 따라 해당 무게가 없으면 기본값이 최대 무게 + 1이 되어
dp배열의 첫번째 항이 0 : 0이기 때문에 dp_w + w에서 무조건 처음 등장하는 무게가
최대 무게보다 작거나 같은 경우 무조건 dp배열이 갱신될 수 있다
🧠 기억하자
내겐 아직 정말 너무 먼, 너무 어려운 그대였던 문제
그래서 아주 많이 찾아봤다! 그래봤자 이정도긴 하지만..
이걸 다 찾아보고 이해하는 것만도 힘들었다..
아무튼 이번에 공부하며 배운 것은!
-
:= 바다코끼리 연산자
새로 연산한 결과를 바로 그 변수에 대입할 수 있게 해주는 연산자! 오 신기하다 -
딕셔너리 자료형
존재 정도만 알고 있었고, 한 번도 사용해 본적은 없었는데 이번 문제를 찾아보며 활용법을 알게 되었다
배열에 해당값이 없을 경우 기본값을 반환해주는 것을 활용하는 것이 참 신기한 아이디어였다!
이것도 잘 배워놨다가 잘 써먹어봐야지
