12865

날짜 : 2023. 04. 17

사용 언어 : python

 

문제

 

 

코드

import sys

n, k = map(int, sys.stdin.readline().split())
dp = [[0] * (k+1) for _ in range(n+1)]  # 최대무게 k, n개만큼 설정
a = list()
a.append([0, 0])

for _ in range(n):
    a.append(list(map(int, sys.stdin.readline().split())))

for i in range(1, n+1):  # 점검할 물건의 인덱스
    for j in range(1, k+1):  # 수용할 수 있는 무게
        w, v = a[i][0], a[i][1]  # i번째 물건의 무게와 가치
        if j < w:  # 현재 물건이 들어갈 수 없는 경우
            dp[i][j] = dp[i-1][j]  # 그대로
        else:  # 아니라면
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)  # 들어갈 물건의 무게만큼 없을 때 더한 값과 비교
    
print(dp[n][k])

 

 

풀이

- 기존의 1차원 배열이 아닌 2차원 배열을 활용한 다이나믹 프로그래밍을 활용해서 풀이한다.

- 우선 배열 a에 각각의 물건의 무게와 가치를 입력받는다.

- 그리고 dp에 대한 메모이제이션을 통해 문제를 풀이한다.

- dp[i][j]는 i번째 물건 차례에서, 무게제한이 j일 때 해당 배낭의 가치를 산정한 값을 의미한다.

- 그렇게 각각 점검할 물건에 대한 for문을 돌리고 그 안에서 0부터 k까지의 무게제한을 두었을 때의 값을 비교하면서 최신화를 진행하고 i번째 물건을 넣을 차례이고 무게제한이 j라고 가정한 상황에서 두 가지 경우의 수가 발생한다.

 

1) i번째 물건을 넣으면 무게가 초과되는 경우 : 이전 물건을 체크했을 때 동일한 무게제한의 가치로 갱신한다.

-> dp[i][j] = dp[i-1][j]

2) i번째 물건을 넣을 때 무게가 초과되지 않는 경우 : 해당 물건을 넣었을 때의 가치와, 이전물건에서의 해당 무게제한일 때의 가치를 비교하여 가치를 갱신한다.

-> dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)

* 여기서 (j-w)를 사용하는 경우는 이전 물건에서 for문을 1부터 (k+1)까지 진행하면서 전체 무게제한에 대해 전부 갱신을 했기 때문에 해당 무게를 차감함으로써 가치를 생신 가능하다.

(예를들어 dp[2][3] = 100,000 이고 무게초과 및 가치가 적은 이유로 갱신이 어렵다면 dp[2][k]까지 100,000으로 갱신된다.)

 

- 이렇게 이중 for을 반복하여 i번째 물건을 탐색할 때 1부터 k까지 무게제한을 걸었을 경우의 케이스를 전부 갱신하고, 마지막에 dp[n][k]를 통해 최종 값을 출력한다. (이는 n의 최대값이 100, k의 최대값이 100,000이기 때문에 가능)

 

 

알게된 점

- 기존 DP문제를 1차원 배열을 활용해서 풀이해서 이를 활용해 풀어보려고 했다.

- 근데 계속 고민해봐도 하위 무게들을 더했을 때를 어떻게 구현할 지 아이디어가 떠오르지 않았다.

- visited[n] = True를 활용해서 반복을 하는 경우 메모리가 굉장히 낭비될 것이고 메모리 초과, 혹은 TLE가 발생할 것이 뻔했기 때문이다.

- 그래서 풀이를 참고했고, 2차원 배열을 활용하여 dp[i][j]가 i번째 물건을 체크하는데, 무게제한이 j일 때의 배낭 가치를 산정한다는 아이디어를 얻을 수 있었다.

- 가장 대표적인 다이나믹 프로그래밍 문제인 만큼 주말에 복습해서 머릿속에 깊이 남겨야겠다.

 

 

 

참고 사이트

- https://hongcoding.tistory.com/50

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