[백준] 1450 냅색문제

문제

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

입력

n: Int = 물건의 개수
c: Int = 가방의 용량
arr: [Int] = 물건의 무게들

1 <= n <= 30 

1 <= c <= 10^9

1 <= arr[i] <= 10^9

결과

ans: Int = 가방에 넣는 방법의 수

해석

n이 크지 않아 조합으로 도전하려 했지만  ({{30}C_1} ~ {{30}C_{30}}) 까지 구한다고 하면 너무 많은 시간이 걸릴 것
같아 실패했다.

 

여기서 비슷하게 느꼇던 문제가 생각났는데 바로 아래 문제다.

프로그래머스

 

이 문제는 두 플레이어가 주사위들을 나눠가진 후 그 주사위 눈들의 합을 합쳐 승/무/패를 계산하는 문제이다.

 

여기서 모든 주사위 조합을 구한 후 마지막에 A의 주사위를 가지고 B의 승무패를 이진 탐색으로 계산했다. 

 

이 문제도 비슷한 것 같다.

 

n을 반씩 나누어서 시간복잡도를 줄일 수 있다.

예를 들어 [1, 2, 3, 4] 라는 무게가 주어졌고 c = 5라고 해보자.

[1, 2]와 [3, 4]를 나누어서 가방에 넣을지 말지를 고민한다.

 

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

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

 

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

[3, 4] 일 때,

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

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

 

여기서 보면 [0,1,2,3] 덩어리에 더 큰 값을 넣을 수록 짧아지는 것을 볼 수 있다

 

즉,  target = c - 현재 넣을려는 무게 일 때,  [0,1,2,3] 덩어리에서 target보다  = upperbound 바로 전 까지

 

여기서 보면 4 직전까지 몇개의 원소가 있는 지 궁금하면 

3에 대한 upperbound를 찾으면된다 = 첫 4의 index = 6  ,  그냥 upperbound자체가 정답이된다.

index가 0부터 시작하는 특성때문에 이득본 것 

 

우리는 그러면 크게 두 단계의 작업을 해야한다.

 

1. 무게를 2등분 하여 나올 수 있는 모든 합을 구한다.  (dfs) 
2. 이분 탐색을 통해 upperbound를 구한다.

 

코드

import Foundation

let nc = readLine()!.split{$0 == " "}.map{Int($0)!}

let (n,c) = (nc[0], nc[1])

let weights: [Int] = readLine()!.split{$0 == " "}.map{Int($0)!}

var sumArray1: [Int] = []
var sumArray2: [Int] = []

func dfs(from i: Int , to j: Int, array: inout [Int], weight: Int) {

    if weight > c  { // 무게 초과 조합 실패
        return
    }
    
    if i == j { // 목표 도달 시 종료
        array.append(weight)
        return
    }
    
    // 해당 무게를 골랐을 때랑 고르지 않을 때 , 두 갈림길로 분기
    dfs(from: i+1, to: j, array: &array, weight: weight+weights[i])
    dfs(from: i+1, to: j, array: &array, weight: weight)
    
}

dfs(from: 0, to: n/2, array: &sumArray1, weight: 0)
dfs(from: n/2, to: n, array: &sumArray2, weight: 0)

sumArray1.sort()

func bsUpperbound(arr: [Int], target: Int) -> Int {
    
    var start = 0
    var end = arr.count
    
    while start < end {
        let mid = (start+end) / 2
        
        if arr[mid] > target { end = mid }
        else { start = mid + 1}
        
    }
    
    return end
}

var ans: Int = 0

for sum2 in sumArray2 {
    ans += bsUpperbound(arr: sumArray1, target: c-sum2) // sum2를 가방에 담고 남은 공간을 sumArray1 조합으로 채워야하므로  c-sum2
}
print(ans)

 

참고

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

 

이진 탐색 ( + 하한 lower_bound, 상한upper_bound )