[Swift][이분 탐색][중간에서 만나기] 백준 1208번 (부분수열의 합 2)

요구능력

해시와 이분탐색

 

문제풀이

일반적인 부분수열의 합으로 풀기에는 시간복잡도가 2^40까지 나와서 시간초과가 나오게된다.

2^40이 나오는 이유는 이 문제는 더하기, 더하지않기라는 경우의 수밖에 없기때문이다.

 

그렇다면 어떻게 풀어야할까?

나는 여기서 중간에서 만나기라는 개념을 처음 접했는데,

대충 이런개념인것같다.

반을 쪼개서 해시로 dictionary에 값들을 저장해주고,

나머지 반에서 값들을 구하면서 (목표값 - 구한값)을 해시에 저장된 값에서 가져오면 중간에서 만나는(?) 개념이 성립되는것 같다.

 

그리고 문제에서는 크기가 양수인 부분수열이라고 했는데, 아래와 같이 재귀로 sum을 계속 들어가면 하나도 더하지않는 경우(공집합)가 생기므로 s가 0인경우에는 공집합이 생기는 경우를 제거해야한다.

 

후기

아직까지 처음접하는 개념이 많은거같다.. 분발하자!

 

코드

import Foundation
let ns = readLine()!.split(separator: " ").map{Int(String($0))!}
var arr = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = ns[0]
let s = ns[1]

var count = 0
var dict = [Int: Int]()

func rightSeq(_ mid: Int, _ sum: Int){
    if mid == n{
        if dict[sum] != nil{
            dict[sum]! += 1
        }else{
            dict[sum] = 1
        }
        return
    }
    rightSeq(mid + 1, sum + arr[mid]) //더하는 경우
    rightSeq(mid + 1, sum)// 더하지 않는경우
}
func leftSeq(_ st: Int, _ sum: Int){
    if st == n/2{
        if dict[s - sum] != nil{
            count += dict[s - sum]!
        }
        return
    }
    leftSeq(st + 1, sum + arr[st])
    leftSeq(st + 1, sum)
}

rightSeq(n/2, 0)
leftSeq(0, 0)

if s == 0{
    count -= 1
}
print(count)