만득

코딩 공부 정리용

​

© 2021. All rights reserved.

백준 1208 부분수열의 합 2

10 Nov 2021

문제 보러 가기

이분탐색이 응용되는 문제이다. 완전 탐색으로 2^N안에 해결할 수 있지만 이렇게 될 경우 N = 40이기 때문에 시간 초과가 발생하게 된다.

  1. 먼저 좌측과 우측으로 구역을 나눠서 각각에 대해 완전 탐색을 시행해준다. 이렇게만 해도 2^40 -> 2^21로 크게 시간을 단축할 수 있다. 그 후 우측 구역을 오름차순으로 정렬해주자.

  2. 좌측 영역에 대한 부분수열의 합 중에서 하나를 선택하고 이를 LeftSum 이라고 해보자. 우측 영역에 대한 부분수열의 합 중에서 RightSum = S-LeftSum이 되는 RightSum의 갯수를 찾아주면 전체 영역의 부분 수열 중에서 합이 S인 부분수열을 찾는 것과 같다. 이를 모든 LeftSum에 대해서 반복 시행해주면 전체 경우의 수를 찾을 수 있다.

  3. 한가지 유의할 점으로 S가 0일 경우 좌측도 아무것도 선택하지 않고 우측도 아무것도 선택하지 않는 경우가 포함되게 된다. 원소가 존재하지 않을 경우 부분수열이라고 부르지 못하기 때문에 S가 0이면 최종결과에서 1을 빼주면 된다.

//
//  main.swift
//  testttt
//
//  Created by 강현준 on 2021/11/09.
//

import Foundation

let ns = readLine()!.split(separator: " ").map { Int($0)! }
let arr = readLine()!.split(separator: " ").map { Int($0)! }
let n = ns[0], s = ns[1]
var left = [Int]()
var right = [Int]()
var result = 0

comb(index: 0, last: n/2, sum: 0, result: &left)
comb(index: n/2, last: n, sum: 0, result: &right)

right.sort(by: { $0 < $1 })
left.forEach {
    let l = lowerBound(start: 0, end: right.count, val: s-$0, arr: right)
    let r = upperBound(start: 0, end: right.count, val: s-$0, arr: right)
    result += (r-l)
}
if s == 0 { result -= 1 }
print(result)

func comb(index: Int, last: Int, sum: Int, result: inout [Int]) {
    if index == last {
        result.append(sum)
        return
    }
    
    comb(index: index+1, last: last, sum: sum+arr[index], result: &result)
    comb(index: index+1, last: last, sum: sum, result: &result)
}

func lowerBound(start: Int, end: Int, val: Int, arr: [Int]) -> Int {
    if start >= end { return end }
    
    let mid = (start+end)/2
    if arr[mid] >= val { return lowerBound(start: start, end: mid, val: val, arr: arr) }
    else { return lowerBound(start: mid+1, end: end, val: val, arr: arr) }
}

func upperBound(start: Int, end: Int, val: Int, arr: [Int]) -> Int {
    if start >= end { return end }
    
    let mid = (start+end)/2
    if arr[mid] > val { return upperBound(start: start, end: mid, val: val, arr: arr) }
    else { return upperBound(start: mid+1, end: end, val: val, arr: arr) }
}

Related posts