[복기] 12865번: 평범한 배낭

문제

백준 12865번: 평범한 배낭

알고리즘 분류

• 다이나믹 프로그래밍
• 배낭 문제

솔루션

input = sys.stdin.readline

n, k = map(int, input().split())
products = [list(map(int, input().split())) for __ in range(n)]

dp = [[0] * (k + 1) for __ in range(n)]
for i in range(n):
    for j in range(0, k + 1):
        if j >= products[i][0]:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - products[i][0]] + products[i][1])
        else:
            dp[i][j] = dp[i - 1][j]

print(max(dp[n - 1]))

• 유명한 배낭 문제
• 2차원 배열 dp를 만들고, 무게마다 최댓값을 계산해서 저장
• dp의 최댓값을 출력하면 끝

96% 틀렸습니다.

96%에서 자꾸 틀렸는데 질문 게시판에서 해답을 찾았다.

https://www.acmicpc.net/board/view/114723

• 입력
  1 5
  1 10
• 정답
  10

그러나 내 코드는 50을 출력한다. 최근에 추가된 반례라서 96%에서 틀린 모양이다. 위 입력에서 dp = [0, 10, 20, 30, 40, 50] 으로 10이 계속해서 더해지는 형태이다. dp[i-1]이 dp[-1] == dp[0]이 되면서 dp의 i번째 줄을 스스로 참조하는 형태가 되버린 것이다. 그래서 그냥 dp 마지막에 빈 배열을 하나 추가해서 해결했다.

input = sys.stdin.readline

n, k = map(int, input().split())
products = [list(map(int, input().split())) for __ in range(n)]

dp = [[0] * (k + 1) for __ in range(n+1)] # n => n+1
for i in range(n):
    for j in range(0, k + 1):
        if j >= products[i][0]:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - products[i][0]] + products[i][1])
        else:
            dp[i][j] = dp[i - 1][j]

print(max(dp[n - 1]))