[알고리즘] Swift -백준 #1182 (부분수열의 합) -조합/브루트포스/백트래킹

문제링크

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

 

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

 

---

분석

n개의 정수로 이루어진 수열이 있을 때

부분 수열 중 수열의 원소를 다 더한 값이 S가 되는 경우의 수구하기

n = 5, s = 0일 때

-7 -3 -2 5 8 이면

5개의 정수를 가지고 더한 값이 0이 되는 경우의 수를 찾기

-3 -2 5를 선택하여 더하면 합이 0

 

풀이 과정

조합을 가지고 모든 부분수열을 구하여 합이 S와 같은 조합을 찾는다

 

 

풀이

combination 조합 구현 출처 : https://developer-p.tistory.com/145

func combination(_ nums: [Int], _ targetNum: Int) -> [[Int]] {
    var result = [[Int]]()
    
    func combi(_ index: Int, _ nowCombi: [Int]) {
        if nowCombi.count == targetNum {
            result.append(nowCombi)
            return
        }
        for i in index..<nums.count {
            combi(i + 1, nowCombi + [nums[i]])
        }
    }
    
    combi(0, [])
    
    return result
}

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

var count = 0
for i in stride(from: 1, to: n+1, by: 1) {
    let combi = combination(arr, i)
    
    for j in combi {
        var sum = 0
        for r in 0..<j.count {
            sum += j[r]
        }
        if sum == s {
            count += 1
        }
    }
}

print(count)

 

결과

for 반복문을 많이 돌렸더니 시간이 매우 오래걸림

 

알게된 점

파이썬에는 간단하게 쓰이는 조합과 순열이 스위프트에는 없어서 구현을 직접해줘야한다... 진짜 파이썬의 행복이었ㄷ구만...

 

 

다른 풀이 

재귀함수를 이용한 백트래킹

let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = input[0], S = input[1]
let series = readLine()!.split(separator: " ").map{Int(String($0))!}

func findNumber(i: Int, sum: Int) -> Int {
    var count = 0
    if sum == S {
        count += 1
    }
    for index in i+1..<series.count {
        count += findNumber(i: index, sum: sum + series[index])
    }
    return count
}

var count = 0
for i in 0..<N {
    count += findNumber(i: i, sum: series[i])
}
print(count)

시간차이가 어마어마하는 구만