백준 1450 냅색문제

출처: www.acmicpc.net/problem/1450

분류: 이분탐색

---

접근방식

n이 30으로 크기 때문에 그대로 부분합을 구하면 2^30 시간제한을 통과하기 어렵습니다.

따라서 반반 나눈 뒤 이분탐색으로 접근하는 방법으로 접근합니다.

 

부분합은 재귀적으로 구해줬습니다.

func partition(_ idx: Int, _ to: Int, _ array: inout [Int], _ sum: Int) {
    guard sum <= nc[1] else { return }
    guard idx < to else { array.append(sum); return }
    
    partition(idx+1, to, &array, sum + products[idx])
    partition(idx+1, to, &array, sum)
}

var sumA = [Int]()
var sumB = [Int]()
partition(0, products.count/2, &sumA, 0)
partition(products.count/2, products.count, &sumB, 0)

 

 

이렇게 반을 나눠 부분합을 구했다면, 

한 쪽에서 부분합을 선택하고 나머지 배열에서 몇 개를 넣을 수 있는지 세어주면 됩니다.

func binarySearchUpperBounds(target: Int) -> Int {
    var low = 0
    var high = sumB.count
    
    while low < high {
        let mid = (low + high)/2
        if target < sumB[mid] {
            high = mid
        } else {
            low = mid+1
        }
    }
    
    return low
}

 

참고로 처음에 예제의 답이 왜 3인지 몰랐었는데요, 배낭에 아무것도 넣지 않는 경우도 하나의 경우로 생각해줘야 합니다 :)

 

해결방법

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

func partition(_ idx: Int, _ to: Int, _ array: inout [Int], _ sum: Int) {
    guard sum <= nc[1] else { return }
    guard idx < to else { array.append(sum); return }
    
    partition(idx+1, to, &array, sum + products[idx])
    partition(idx+1, to, &array, sum)
}

var sumA = [Int]()
var sumB = [Int]()
partition(0, products.count/2, &sumA, 0)
partition(products.count/2, products.count, &sumB, 0)

sumB.sort()

func binarySearchUpperBounds(target: Int) -> Int {
    var low = 0
    var high = sumB.count
    
    while low < high {
        let mid = (low + high)/2
        if target < sumB[mid] {
            high = mid
        } else {
            low = mid+1
        }
    }
    
    return low
}

var getCase = 0
for a in sumA {
    
    let upper = binarySearchUpperBounds(target: nc[1] - a)
    getCase += upper
}

print(getCase)

 

배운점

이런 방식을 meet in the middle 방법이라고 한다더라.