[Algorithm] 백준 12865번 평범한 배낭(파이썬)
얼마 전 한 부트캠프 코테를 보고 처참하게 말아먹었다...ㅋ
그래서 고등학교 친구에게 SOS를 쳤다.
나랑 매일 1일 1코테하고 서로 발표할래? (끄덕끄덕)
친구가 개인적인 사정으로 담주부터 시작하자고 했는데... 나 또 날 잘 알잖아?
하루 밀리면 가차없이 밀릴 나를 너무 잘 알기에 오늘부터 하나씩 업로드해놓아야한다...
이 배낭 문제가 유명한 문제인 것은 안다... 왜냐면 나도 어렷한 알고리즘 수강생이기 때문이다.
그러나 코드화해보는 것은 이번이 처음이다. 그리고 DP를 풀어보는 것도 사실 창피하지만 처음이다..ㅠㅠ
그래서 차근차근히 해보도록 하겠다!!
입력값 코드화하기
ex) 만약 K가 7이라면, 준서는 7kg을 버틸 수 있다는 말이다.
첫 번째 입력을 받아볼까?
N, K = map(int, input().split())
두 번째는 물건의 무게 W, 그에 대한 가치를 부여하는 것이다.
사실 국어 능력이 매우 딸리는 나는... 솔직히 왜 무게를 드는데 기분이 좋니...? 라는 생각을 하게 되었다...ㅋ
그냥 이런 헬창이 있다고 생각하자...ㅋ
어쨌든 두 번째 입력을 받아볼까?
bag = [list(map(int, input().split())) for _ in range(N)]
# [[6, 13], [4, 8], [3, 6], [5, 12]]
이렇게 입력 받았을 때 문제를 이어가야 다음을 넘어갈 수 있을 것이다.
문제 이해하기
뭔가 배열을 이용할 것 같다는 느낌은 든다.
다음과 같은 배열이 있을 때,
[6, 13] 입력값이 주어졌다는 의미 → 6kg의 짐이 들어온다
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 0 | 0 | 0 | 0 | 13 | 13 |
인덱스 1 → 1kg의 가방에 6kg짐은 들어올 수 없다 → 0
인덱스 2 → 2kg의 가방에 6kg짐은 들어올 수 없다 → 0
...
인덱스 5 → 5kg의 가방에 6kg짐은 들어올 수 없다 → 0
그러나,
인덱스 6 → 6kg의 가방에 6kg짐은 들어올 수 있다 → 가치 13 넣어주기
인덱스 7 → 7kg의 가방에 6kg짐은 들어올 수 있다 → 가치 13 넣어주기
한 줄의 최댓값은? 13
[4, 8] 입력값이 주어졌다는 의미 → 4kg의 짐이 들어온다
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 0 | 0 | 8 | 8 | 13 | 13 |
인덱스 1 → 1kg의 가방에 4kg짐은 들어올 수 없다 → 0
인덱스 2 → 2kg의 가방에 4kg짐은 들어올 수 없다 → 0
...
인덱스 4 → 4kg의 가방에 4kg짐은 들어올 수 있다 → 가치 8 넣어주기
인덱스 5 → 5kg의 가방에 4kg짐은 들어올 수 있다 → 가치 8 넣어주기
그렇다면? 인덱스 6일 때와 7일 때는??
인덱스 6 → 6kg의 가방에 4kg짐은 들어올 수 있다 → 가치 8 넣어주기 vs. 가치 13넣어주기
인덱스 7 → 7kg의 가방에 4kg짐은 들어올 수 있다 → 가치 8 넣어주기 vs. 가치 13넣어주기
이렇듯 max 값을 넣어준다.
한줄의 최댓값은? 13
[3, 6] 입력값이 주어졌다는 의미 → 3kg의 짐이 들어온다
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 0 | 6 | 8 | 8 | 13 | 13 |
인덱스 1 → 1kg의 가방에 3kg짐은 들어올 수 없다 → 0
인덱스 2 → 2kg의 가방에 3kg짐은 들어올 수 없다 → 0
인덱스 3 → 3kg의 가방에 3kg짐은 들어올 수 있다 → 가치 6 넣어주기
인덱스 4 → 4kg의 가방에 3kg짐은 들어올 수 있다 → 가치 6 넣어주기 vs. 가치 8 넣어주기
인덱스 5 → 5kg의 가방에 3kg짐은 들어올 수 있다 → 가치 6 넣어주기 vs. 가치 8 넣어주기
인덱스 6 → 6kg의 가방에 3kg짐은 들어올 수 있다 → 가치 6넣어주기 vs. 가치 13넣어주기
그러나
인덱스 7 → 7kg의 가방에 3kg짐은 들어올 수 있다 → 가치 6넣어주기
+ 4kg짐도 들어올 수 있다 → 가치 8 넣어주기
→ 가치 14넣어주기 vs. 가치 13넣어주기
자, 이를 통해 DP를 해야겠다는 감이 오지 않는가?
DP 코드화
① dp 이차원 배열을 만들어라.
dp = [[0] * (K+1) for _ in range(N+1)]
② for문을 통해 값을 입력해보자
for i in range(1, N+1):
for j in range(1, K+1):
만약 j가 들어오는 무게보다 크면?
if j >= bag[i-1][0]:들어오는 값의 가치와 dp 배열의 이전 가치와 비교
dp[i][j] = max(bag[i-1][1], dp[i-1][j])그러나! 아까 어떻게 했지?
dp[i - 1][ j - < ? >] → < ? > : bag[i-1][0]
작으면
0 → 이전 값을 가져온다? dp 배열의 이전 가치 (dp[i-1][j])
else:
dp[i][j] = dp[i-1][j]최종
N, K = map(int, input().split())
bag = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * (K+1) for _ in range(N+1)]
for i in range(1, N+1):
for j in range(1, K+1):
if j >= bag[i-1][0]:
d[i][j] = max(bag[i-1][1] + dp[i-1][j-bag[i-1][0]], dp[i-1][j])
else:
dp[i][j] = dp[i-1][j]
print(dp[N][K])