백준 12865 평범한 배낭 파이썬 풀이

난이도 : 골드5

풀이일 : 2402073

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

오답 코드 -> 96% 틀렸습니다

import sys

N, K = list(map(int, sys.stdin.readline().split()))
info = []

for _ in range(N):
    W, V = list(map(int, sys.stdin.readline().split()))
    info.append([W, V])

dp = [[0] * (K + 1) for _ in range(N)]

for i in range(N):
	weight = info[i][0]
    value = info[i][1]
    for j in range(K + 1):    
        if j < weight:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight] + value)

print(dp[N - 1][K] if dp else 0)

• info : 물건의 무게와 가치를 저장할 2차원 배열
• dp : 각 무게별 최대 가치를 저장할 2차원 배열
• 이중 반복문
  • 물건의 개수 만큼 반복하며 이번 물건의 weight, value 정보 저장
  • 무게 만큼 반복하며 해당 무게를 가방에 넣을 수 없다면 이전 i 에서의 같은 j 값의 최대 가치 저장
  • 해당 무게를 가방에 넣을 수 있다면, 현재 물건을 넣을 수 있는 최대 가치 값과, 이전 i 에서의 같은 j 값 중 최대 가치 저장
• dp가 존재한다면 dp[N - 1][K]를 출력, 아니면 0 출력

---

풀이 코드

import sys

N, K = list(map(int, sys.stdin.readline().split()))

# 물건 정보 저장
info = [[0, 0]]
for _ in range(N):
    W, V = list(map(int, sys.stdin.readline().split()))
    info.append([W, V])

# 각 무게의 최대 가치 저장
dp = [[0] * (K + 1) for _ in range(N + 1)]

# 물건의 개수 + 1 만큼 반복하며 무게, 가치 저장
for i in range(N + 1):
    weight = info[i][0]
    value = info[i][1]
    # 무게만큼 반복
    for j in range(K + 1):
        # 현재 무게 가방에 넣을 수 없다면, i-1의 최대가치 저장
        if j < weight:
            dp[i][j] = dp[i - 1][j]
        # 현재 무게 가방에 넣을 수 있다면,
        # i-1의 최대가치와 현재 물건을 넣은 최대 가치 중 큰 값 저장
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight] + value)

print(dp[N][K])

코드 변화

• info 초기 상태에 [0, 0]을 추가한 뒤 물건의 정보 입력
• dp 초기 상태의 열을 N + 1 열로 한 줄 추가
• 이중 반복문의 i 범위를 N + 1까지로 수정
• dp[N][K]로 수정

---

느낀점

• 오랜만에 푼 파이썬 알고리즘인데 처음에는 DFS로 현재 물건을 넣는 경우, 안넣는 경우로 구분해 풀었다가 반례에서 시간초과가 발생했다.
• 두 번째로 푼 건 처음에는 물건이 주어지지 않을 때 문제가 발생해 수정하였는데, 아직도 왜 틀렸는지 잘 모르겠어서 조금 더 공부가 필요한 상태다.
• 이제 이런 비슷한 유형의 문제들로 또 한동안 성실하게 풀어야지