[1208] 부분 수열의 합 2

toru·2022년 9월 22일
0
1 <= n <= 40
-> 시간초과  2^40 
-> 반으로 쪼개서 처리한다.

[2251] 물통이 생각난다.
물통c에만 물이 가득하고 나머지a,b는 비어있다면
물의 양은 물통a = a, 물통b = b, 물통c = c-a-b로 정의할 수 있었다.

배열을 반으로 나눠서 먼저 왼쪽배열의 경우의 수 와 중복을 기록한다(a).
target을 만드는 경우의 수가 왼쪽과 오른쪽에 걸처 존재한다면,
target(c) - sum(b), 즉 a와 겹치는 경우의 수가 있을 것이다.

target이 0일 경우, 포함하거나 안하는 처리(bs(s+1, e, sum, RL))에서
0에 의미없이 1이 들어가기 때문에 이를 예외처리 한다.
let p = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n,target) = (p[0],p[1])
let arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var dict = [Int:Int]()
let mid = n/2
var cnt = target == 0 ? -1 : 0

func bf(_ s:Int,_ e:Int,_ sum:Int,_ LR:String) {    // 조합
    if s == e {
        switch LR {
        case "L": dict[sum,default: 0] += 1
        default : cnt += dict[target-sum,default: 0]
        }
        return
    }
    bf(s+1, e, sum, LR)
    bf(s+1, e, sum + arr[s], LR)
}
bf(0, mid, 0, "L")
bf(mid, n, 0, "R")
print(cnt)
profile
iOS

0개의 댓글