[백준] 12865번 평범한 배낭 (파이썬)

< 백준 12865번 평범한 배낭 - 파이썬 풀이 >

• 해당문제 링크

  목차

1. 문제풀이 아이디어
2. 코드구현

문제풀이 아이디어

• 먼저 문제에서 요구하는 것을 알아보자. 문제를 풀어보면 물건은 무게 W, 가치 V를 가진다. 이런 물건이 N개가 있을때 용량이 K인 배낭에 물건을 넣으려 한다. 물건의 넣을 수 있는 모든 경우 중 배낭안에 들어간 물건의 가치가 가장 높은 경우는?

• 결국은 가능한 모든 경우의 수를 구해야 최대 값을 구할 수 있다. 모든 경우의 수를 구하기 위해 생각할 수 있는 방법은 조합, 백트래킹, DP, 브루트 포스 정도를 생각할 수 있다.

• 문제에서 주어진 시간 제한은 2초이고 물품의 최대 수는 100, 버틸 수 있는 무게는 100,000이다.

• 백트래킹, 브루트 포스 등은 정확한 시간 복잡도를 구할 수 없지만 조합과 비슷한 시간 복잡도를 보일 것 같다. 결국은 이것들도 모든 경우의 수를 찾는 방법이기 때문이다.

• 조합은 서로 다른 n개 중 순서 생각하지 않고 r개를 택하는 경우의 수를 의미하고 O(2^N)이란 시간 복잡도를 가진다. N이 조금만 커져도 실행시간이 길어지기 때문에 최대 100인 해당 문제에선 사용할 수 없다.

• 그렇다면 DP( Dynamic Programming )을 이용해보자. DP란 이전의 연산 결과를 다음 연산에 사용함으로써 중복되는 연산의 수를 줄여주는 방식이다. DP는 탑다운 방식과 바텀업 방식이 존재한다. 두 가지 방식의 시간, 공간 복잡도는 거의 같다. 필자는 바텀업 방식이 더 편하여 이를 이용해보겠다.

• 바텀업이란 작은 크기의 연산부터 큰 크기로 커져나가면서 값을 도출하는 방식이기에 작은 크기의 연산이 무엇인지를 찾아야한다. 유의미한 작은 크기의 연산을 찾기 위해서 이 문제에서 최대값을 구할때 어떤 요소에 의해서 값이 달라질지를 생각해보자.

• K = 0인 경우를 생각해보면 최대값이 얼마일까? 무조건 0일 것이다. 배낭에 물건을 못넣기 때문이다.

• N = 0인 경우를 생각해보면 최대값이 얼마일까? 마찬가지로 0일 것이다. 배낭에 넣을 물건이 없기 때문이다.

• K = 1이 되면 1의 무게의 물건 중 가치가 가장 높은 것의 값이 될 것이다.

• N = 1이면 이 물건의 무게가 K보다 작다면 이 물건이 될 것이다.

• 즉, 해당 문제의 최대값은 K, N에 의해서 달라진다는 것이다. 그렇다면 써야하는 요소가 두 개이기 때문에 상태를 표현하기 위해선 이 두 요소를 모두 사용해야한다.

• 앞서 봤던 작은 연산의 경우를 seed 값과 두 요소를 이용해서 2차원 dp 테이블을 만들어보자.

  	0	1	2	3	4	5	6	7
  0	0	0	0	0	0	0	0	0
  1	0	0	0	0	0	0	0	0
  2	0	0	0	0	0	0	0	0
  3	0	0	0	0	0	0	0	0
  4	0	0	0	0	0	0	0	0

• dp 테이블 인덱스의 값으로 최대 가치를 넣을 것이다. seed 값으로 K = 0, N = 0 일때를 전부 0으로 넣었다. (초기화를 하면서)

• 이제는 어떻게 진행해나가야할까? K, N의 최소값이 1이기에 1부터 각 주어진 값까지 반복하면서 최대값을 비교를 해야하는데 지금 인덱스의 위치의 값은 현재 물건을 넣지 않고 이전 물건을 넣었을때 K에서의 값과 이전 물건을 넣지 않고 현재 물건을 넣었을때 K에서의 값과 현재 K보다 1작은 K까지의 값 중 최대 값이 가능한 모든 경우에서의 최대 값인 것이다.

• 내가 K=1, N=1 ( 4, 6 )에서의 최대 값을 생각해보자. 0일 것이다 물건의 무게가 4라서 그렇다. 그럼 K=4면?? 최대 값은 6일 것이다. 여기에서 물건이 추가된다고 생각을 하면서 문제를 풀어보자.

코드구현

def solution():
    for i in range(1, N+1):
        weight, value = things[i-1]
        for j in range(1, K+1):
            if j - weight >= 0: dp[i][j] = max(dp[i-1][j-weight]+value, dp[i][j-1], dp[i-1][j])
            # 지금 인덱스의 위치의 값은 현재 물건을 넣지 않고 이전 물건을 넣었을때 K에서의 값과 이전 물건을 넣지 않고 현재 물건을 넣었을때 K에서의 값과 현재 K보다 1작은 K까지의 값 중 최대 값이 가능한 모든 경우에서의 최대 값을 의미
            else: dp[i][j] = dp[i-1][j]
            # 현재 물건이 들어갈 수 없는 배낭의 용량일땐 그저 이전 물건이 처리했던 값을 넣어줘야 이전 용량(dp[i][j-1])에서의 최대 값을 갱신할 수 있다.
    return dp[N][K]
if __name__ == "__main__":
    N, K = map(int, input().split())
    things = [list(map(int, input().split())) for _ in range(N)]
    dp = [[0]*(K+1) for _ in range(N+1)]
    print(solution())