1182번: 부분수열의 합

문제 풀이 아이디어

이 문제를 처음에 파이썬으로 풀었을 때는 조합으로 풀었었습니다. 조합으로 풀었던 이유는 다음과 같습니다.

1. 우리가 관심 있는 것은 수열의 “합”입니다. 따라서 수열의 순서는 아무런 상관이 없습니다.
2. 수열의 길이 역시 1 ~ N까지 모든 수열을 찾아봐야 합니다.
3. 따라서 모든 길이의 조합을 구해서 더 해보는 방법을 사용해봅시다.

스위프트로 조합 구현하기

조합을 내장하고 있는 파이썬과는 달리 스위프트는 조합을 직접 구현해서 사용해야 합니다. 순열과 마찬가지입니다.

순열과 구현하는 방식이 거의 유사합니다. 다만 순열은 순서가 다르면 다른 순열이지만 조합은 순서가 없으므로 처음에 방문한 index는 다시 방문할 필요가 없습니다. 따라서 dfs에서 현재 index를 인자로 넘기고 그 다음부터만 반복문을 돌립니다.

// 조합을 구하는 함수
    // array: 조합을 구하고자 하는 대상 (정수, 문자열)등을 배열에 담아 전달
    // length: 원하는 조합의 길이
func combination<T: Comparable>(of array: Array<T>, length: Int) -> [[T]] {
    var result = [[T]]() // 👉 결과를 담을 배열
    
    // dfs를 수행하는 함수
    func combi(nowIndex index: Int, _ now: Array<T>) {
        // 재귀함수 탈출 조건 = 현재의 조합의 길이가 원하는 조합의 길이와 동일
        if now.count == length {
            result.append(now)
            return
        }
        
        // array를 전부 순환하는 것이 아니라 index부터 순회하므로
        // 순열과는 달리 방문 체크하는 배열 없이도 중복되지 않게 할 수 있다.
        for i in index..<array.count {
            combi(nowIndex: i + 1, now + [array[i]])
        }
    }
    
    combi(nowIndex: 0, [])
    
    return result
}

풀이

// 부분 수열의 합

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

// 모든 길이에 대하여 조합을 구하기
for length in 1...N {
    let combinations = combination(of: nums, length: length)
		// 길이가 length인 조합을 모두 순회하면서
    for combination in combinations {
        if combination.reduce(0, +) == S { //👉 합이 S와 동일하면 
            result += 1 //👉 결과에 +1
        }
    }
}

print(result)

🤔 그런데???

둘 다 조합을 활용해서 푼 문제인데 파이썬 보다 스위프트가 느렸습니다… 시간 제한이 2초라서 정답을 받기는 했습니다만, 그래도 다른 방법을 찾아보기로 했습니다.

다른 풀이

구글링을 통해 더 최적화된 풀이를 찾을 수 있었습니다. dfs를 통해 완전 탐색을 하는 방식입니다.
주어진 각 숫자에 대해서 “부분 수열에 넣는 경우” vs “넣지 않는 경우”를 완전 탐색하는 방법이라고 보면 됩니다!

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

var count = 0
var sum = 0

func dfs(length: Int, now: Int) {
    // 재귀함수 탈출 조건
        //👉 합이 S일 때
        //👉 그리고 수열의 길이가 0 이상일 때 (S가 0일 때 바로 리턴되는 것을 방지)
        //⭐️ 탈출 조건이라고 리턴해버리면 안된다! (뒤에 숫자가 더 붙어서 답이 될 수도 있으니까)
    if sum == S && length > 0 {
        count += 1
    }

    // 겹치면 안되니까 now부터 반복문을 돌린다.
    for i in now..<N {
        sum += nums[i] //👉 합에 더한다.
        dfs(length: length + 1, now: i + 1) //👉 그 다음 index부터 순환한다.
        sum -= nums[i]
    }
}

dfs(length: 0, now: 0)
print(count)

🙏 참고한 블로그

[Swift][BruteForce] 백준 1182번 (부분수열의 합)