[BOJ] 백준 1450 냅색문제 (Swift)

문제

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

1450번: 냅색문제

풀이

이 문제는 dfs + 이분탐색으로 풀이할 수 있습니다.

n이 최대 30이므로, 모든 경우의 수를 고려하면 $2^30$ = 약 10억의 비용이 드므로 시간초과가 나올 것입니다.
어떻게 시간복잡도를 줄일 수 있을까요?

n을 반씩 나누어서 시간복잡도를 줄일 수 있습니다.
예를 들어 [1, 2, 3, 4] 라는 무게가 주어졌다면,
[1, 2]와 [3, 4]를 나누어서 가방에 넣을지 말지를 정해줍시다.

[1, 2] 에 대해서 경우의 수를 구한다면 4개가 나올 것이고, 각각 무게는 [0, 1, 2, 3] 이 나올 것 입니다.
[3, 4] 에 대해서 경우의 수를 구한다면 4개가 나올 것이고, 각각 무게는 [0, 3, 4, 7] 이 나올 것 입니다.

이제 이 두가지 무게를 가지고 가방에 넣는 방법을 구할 수 있습니다.

가방에 최대 5만큼 넣을 수 있다고 가정한다면 어떤 방법으로 구할 수 있을까요?

[3, 4]에 대해 구한 무게를 가지고 접근해보겠습니다.

[3, 4] 일 때,

1. 가방에 0을 넣으면 [1, 2]에서는 [0, 1, 2, 3] 총 4개를 넣을 수 있습니다.
2. 가방에 3을 넣으면 [1, 2]에서는 [0, 1, 2] 총 3개를 넣을 수 있습니다.
3. 가방에 4를 넣으면 [1, 2]에서는 [0, 1] 총 2개를 넣을 수 있습니다.
4. 가방에 7을 넣으면 [1, 2]에서는 아무것도 넣을 수 없습니다.

그러면 4 + 3 + 2 총 9개의 경우의 수가 존재하게 됩니다.

가방에 최대 넣을 수 있는 무게 - [3, 4]의 무게에 대해서 [1, 2]의 무게의 upperbound를 구해주는 것과 동일합니다.

소스코드

후기

맨 처음 풀이할 때, 가방에 넣을지 말지 모든 경우의 수를 구하는 방식으로 풀이해서 시간초과를 받았습니다.
n이 최대 30이므로 $2^30$은 약 10억이기 때문에 당연하다고 생각했습니다.

풀이과정을 떠올리지 못해서 여러 글들을 참고하고 풀이했는데, 이러한 풀이방법이 있어서 신박했습니다.