BOJ-1450 냅색문제 Swift

문제

세준이는 N개의 물건을 가지고 있고, 최대 C만큼의 무게를 넣을 수 있는 가방을 하나 가지고 있다.

N개의 물건을 가방에 넣는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다.

출력

첫째 줄에 가방에 넣는 방법의 수를 출력한다.

내가 푼 풀이

접근방법 1: 브루트포스(조합) (시간초과)

N = 30이니까 밑져야본전식으로 가능한 모든 물건 합산의 경우의수를 구해봤지만 시간초과가 났다.

 

접근방법 2: Meet in the Middle / 이분탐색 / 조합

이 문제에서 새롭게 알게된 알고리즘이 있는데 바로 Meet in the Middle이다.

이 알고리즘은 브루트포스를 이용하기에 경우의수가 매우 많은경우 분할하여 연산횟수를 줄이는 기법이다.

접근방법 1번대로 모든 경우의수를 구한다면 $2^{30}$ 만큼 연산이 필요하고 이는 1,073,741,824번으로 시간초과가 발생한다.

이를 절반으로 나누어 경우의수를 구하면

$2^{15}  = 32,786$ 으로 연산횟수를 대폭 감소시킬 수 있다.

두개의 배열로 분할하여 경우의수를 갖는 부분집합을 구한다.

이때, 무게 C보다 큰 수는 불가능한 경우므로 부분집합에 넣지 않는다.

 

1. 주어진 무게의 배열을 절반으로 나눈다.

2. 절반으로 나눈 배열의 부분집합을 구한다.(배열의 원소를 더해서 나올 수 있는 모든 무게의 경우의수)

3. 두개의 부분집합 배열이 생성된다.

 

위 과정을 통해 오른쪽부분집합과 왼쪽부분집합이 구해졌다.

양쪽의 원소를 한개씩 가져와 더한 값이 C보다 작거나 같다면, 이는 가능한 경우의수가 된다.

 

따라서 (C - 오른쪽부분집합의 원소)보다 작거나 같은값은 모두 가능한 경우의 수가 된다.

갯수를 구하기 위해 이분탐색을 활용한다.

부분집합은 중복된 값을 가질 수 있다. 이는 가능한 모든 무게의 경우의수이기 때문이다.

이분탐색을 이용하여 중복된값을 갖는 배열의 가장 뒤에 위치한 인덱스를 구하면 해당 원소보다 작거나 같은 원소의 갯수를 구할 수 있다.

 

코드로 구현하면 다음과 같다.

import Foundation

// 입력받기
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = input[0], C = input[1]
var arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var left = [Int]()
var right = [Int]()
var leftSums = [Int]()
var rightSums = [Int]()
var answer = 0
let mid = arr.count / 2

// 주어진 물건의 배열을 절반으로 나눈다.
for i in 0..<mid {
    left.append(arr[i])
}
for i in mid..<arr.count {
    right.append(arr[i])
}

// 조합
// 조합을 이용해 배열내 모든원소의 합 부분집합을 구한다.
func combi(targetArr: [Int], targetNum: Int, sum: Int, cnt: Int, index: Int, right: Bool) {
    if targetNum == cnt {
        if right {
            rightSums.append(sum)
        } else {
            leftSums.append(sum)
        }
        return
    }
    for i in index..<targetArr.count {
        let total = sum + targetArr[i]
        // 무게 C보다 큰수는 버린다. (불가능한 경우의수 이므로)
        if total <= C {
            combi(targetArr: targetArr, targetNum: targetNum, sum: total, cnt: cnt+1, index: i+1, right: right)
        }
    }
}

// 반으로 나눈 배열의 각 부분집합을 조합을 이용해 구한다.
// 오른쪽 배열
for i in 0...right.count {
    combi(targetArr: right, targetNum: i, sum: 0, cnt: 0, index: 0, right: true)
}
// 왼쪽 배열
for i in 0...left.count {
    combi(targetArr: left, targetNum: i, sum: 0, cnt: 0, index: 0, right: false)
}

// 이분탐색을 위해 정렬
leftSums.sort{$0 < $1}
rightSums.sort{$0 < $1}

// 이분탐색
// 부분집합의 합이 무게 C보다 작아야한다.
// 이는 오른쪽 부분집합 원소 하나를 꺼낸 값이 (C - 왼쪽부분집합의 값) 보다 작거나 같다면 가능한 경우의 수다.
// 이분탐색을 이용해 가능한 경우의수중 가장 큰수의 인덱스를 구한다.
// 여기서 인덱스는 곧 해당 원소보다 작거나 같은 원소의 갯수를 의미하므로 해당 인덱스를 더해준다.
// 중복된 값이 존재하는 이분탐색은 가장 뒤쪽의 인덱스를 구하는방법을 사용하자.
for rNum in rightSums {
    let sub = C - rNum
    var lidx = 0
    var ridx = leftSums.count - 1
    while lidx <= ridx {
        let mid = (lidx + ridx) / 2
        if leftSums[mid] <= sub {
            lidx = mid + 1
        }else {
            ridx = mid - 1
        }
    }
    answer += ridx+1
}

print(answer)