백준 12865번 문제(평범한 배낭) 파이썬(Python) 풀이 [로밍맨]

문제 링크

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

12865번: 평범한 배낭

 

정답 코드는 아래와 같습니다.

def solve():
  n, k = [int(x) for x in input().split()]
  table = [0] * (k+1)
  for _ in range(n):
    w, v = [int(x) for x in input().split()]
    if w > k:
      continue
    for j in range(k, 0, -1):
      if j + w <= k and table[j] != 0:
        table[j+w] = max(table[j+w], table[j] + v)
    table[w] = max(table[w], v)
  print(max(table))
 
solve()
 

 

이 문제는 2차원 DP(Dynamic Programming) 필수 예제라고 할 수 있는 아주 유명한 문제 입니다.

백준에서는 문제 이름이 "평범한 배낭" 이지만, 보통 "배낭 문제" 영어로는 "Knapsack problem" 이라고 합니다.

우리는 이 문제를 어떻게 설계해서 풀어나가는지도 익혀야겠지만, 더 중요한 것은 그러한 풀이를 떠올리는 방법을 익히는 것에 있습니다.

그래야만 다양한 유형, 그리고 새로운 유형에 대하여 실전에서 해법을 떠올릴 수 있을 것이기 때문입니다.

 

문제를 읽고 맨 처음 드는 생각은 아마도 "가장 효율적인(무게 대비 가치가 높은) 물건 위주로 담으면 되는것 아닌가?" 일 것입니다.

왜냐하면 우리는 일상에서 이런 일(한정된 가방에 짐을 싸는 일)을 실제로 자주 겪고, 이에 대하여 실제로 무게 또는 부피 대비 가치가 높은 물건을 담아서 다니곤 합니다.

여행을 갈 때에도, 학교를 갈 때에도, 출근을 할 때에도 말이죠.

하지만 이 방법은 최적값에 근사한 값을 구할 수 있을지는 몰라도 가장 최적 값을 구하지는 못합니다. (문제에서 주어진 예제로 반증됨)

다시 말해서 위에서 말한 방법, 우리가 일반적으로 떠오를 것이고 늘 사용하는 방법은 사실 휴리스틱(heuristics) 이라는 것이죠.

 

그럼 어떻게 해야 할지 다시 생각을 해보겠습니다. 무리하게 풀이 자체를 단번에 떠올리려고 하지 말고, 주어진 예제의 경우에 대해서 어떻게 답을 구해낼 수 있을지, 생각해보자는 뜻입니다.

예제의 경우를 실제로 어떻게 담는게 가장 좋은 것인지 해보다보면 결국 각 물건에 대하여 담거나, 담지 않거나 하는 모든 경우에 대하여 다 확인해보고 있다는 것을 깨닫게 될 것입니다.

이렇게 하면 답을 알 수 있는 것은 분명합니다. 하지만 이 방식은 정답이 아닙니다.

왜냐하면 이 방식은 복잡도가 O(2^N) 인데, 여기서 N 은 worst case 100 이라서, 전체 복잡도가 너무 큰 값이어서 시간 안에 풀리지 않기 때문입니다.

 

풀이가 또 막히네요, 어떻게 해야 할까요? 이런 경우에는 크게 2가지를 봐야 하는데요.

첫 번째로는 주어진 조건 중에 사용하지 않은 조건이 있는가를 살피는 것입니다.

지금까지 위에서 이야기한 풀이 방식에서는 아직 사용하지 않은 조건이 있습니다. 바로 "무게 제한" 이죠.

문제 출제자들은 일반적으로 불필요한 조건을 제공하는 것을 꺼려합니다.

그 이유는 의도하지 않은 방식으로 문제가 풀려버릴 수 있기 때문입니다.

이것을 역으로 생각한다면, 주어진 조건이라면 풀이에 이용될 확률이 매우 높다는 것을 유추할 수 있습니다.

따라서 아직 사용하지 않은 이 조건을 어떻게 사용할 수 있을지를 염두에 두고 풀이를 떠올려 나가야 합니다.

두 번째로는 실제로 naiive 한 방식을 진행해보는 것입니다.

모든 경우에 대하여 다 계산하는 그 방식을 실제로 나열해나가면서 계산을 해나가 보는 것입니다.

위에서는 사람의 입장에서 실제 상황이라고 생각하고 어떻게 풀 수 있을지 계산해본 것이고, 그러다보니 모든 경우에 대해서 다 확인하는 것과 동일하다는 것을 깨달은 것이라면, 여기서는 모든 경우에 대해서 다 해보는 것을 컴퓨터 입장에서 table 을 그려가면서 단계별로 진행해보자는 것입니다.

결국 이렇게 그려가면서 사용하지 않은 조건을 이용하면서 불필요한 연산을 제거할 수 있는지를 확인해보는 것이지요.

그려나가다보면 weight 가 너무 큰 경우에 대해서는 연산을 할 필요가 없다는 것을 알 수 있으며, weight 은 제한적이라는 것을 고려했을 때, 각 경우에 대한 table 이 아니라 weight 에 대한 table 을 그리고 그 table 을 관리한다면,

많은 중복을 제거하면서 문제가 시간 안에 풀린다는 것을 알 수 있습니다.

다시 말해서 각 경우들에 대하여 어떤 경우가 정답인지 알 수 없으므로, table에 모든 무게에 대하여 그 값을 미리 저장해두겠다는 것입니다. 무게 제한이 없다면 모든 무게는 무한대가 되어서 불가능하겠지만, 여기서는 무게 제한이 있기 때문에 가능한 방법입니다.

 

728x90

 

즉, A, B, C, D 가 다음과 같을 때, 각각에 대하여 포함하는 경우를 업데이트해나가는 것입니다.

	weight	value
A	6	13
B	4	8
C	3	6
D	5	12

 

<초기 상태>

weight	A	B	C	D
0	0
1	0
2	0
3	0
4	0
5	0
6	0
7	0

 

<A를 넣었을 때>

weight	A	B	C	D
0	0
1	0
2	0
3	0
4	0
5	0
6	13
7	0

물건이 A 밖에 없다고 가정하였을 때, 넣거나 넣지 않거나 두가지 경우가 있을텐데, 넣지 않은 경우는 초기 상태와 동일할 것이고, 넣는 경우는 무게가 6인 물건을 넣는 것이니, 무게가 6이가 가치가 13인 경우가 있을 것입니다. 물건이 A밖에 없다면 이 중에서 가장 큰 값인 13이 정답이 될 것입니다.

그럼 이번에는 B를 넣는 경우를 생각해보겠습니다(B를 넣지 않는 경우는 현재 상태와 값이 동일하므로 건너뜁니다)

 

<B를 넣었을 때>

weight	A	B	C	D
0	0	0
1	0	0
2	0	0
3	0	0
4	0	8
5	0	0
6	13	13
7	0	0

B를 넣었을 때라고 했지만, 이는 다시 말하자면 물건이 A와 B만 있는 경우를 의미합니다. 여기서 이미 둘 다 넣는 경우에 대해서는 제한 무게를 넘어가므로 계산되지 않고 버려지는 방식으로 계산량을 줄이는 것을 확인할 수 있습니다.

 

<C를 넣었을 때>

weight	A	B	C	D
0	0	0	0
1	0	0	0
2	0	0	0
3	0	0	6
4	0	8	8
5	0	0	0
6	13	13	13
7	0	0	14

B에 있던 값은 그대로 올 것이고, 무게에다가 3을 더해도 7을 넘지 않는 경우(여기서는 무게 4인 경우)에 무게 3을 더하고, value 6을 더해서 무게 7인 위치에 value 14가 업데이트 됩니다.

칸을 채워나가다 보면, 위에서 아래로 채우는 방식보다는 아래에서 위로 채워나가는 방식이 더 적합하다는 것을 알 수 있습니다.

 

<D를 넣었을 때>

weight	A	B	C	D
0	0	0	0	0
1	0	0	0	0
2	0	0	0	0
3	0	0	6	6
4	0	8	8	8
5	0	0	0	12
6	13	13	13	13
7	0	0	14	14

D는 무게가 5 이기 때문에 2부터 그 값을 업데이트 할 수 있습니다. 그런데 2부터 1까지는 모두 value 가 0이기 때문에 아무것도 하지 않으며, 0인 경우만 값일 더하여 그 값을 업데이트 합니다.

정답은 이 중에서 가장 큰 값인 14가 됩니다.

 

풀이는 아래 영상을 참고 바랍니다.

https://www.youtube.com/watch?v=uggO0uzGboY 

 

저작권 라이선스: CC BY (출처만 표시하면 자유롭게 이용 가능)