[PS] 백트래킹 - n과m(11) (12), 부분수열의 합 1182

import Foundation

let nm = readLine()!.split(separator: " ").map { Int($0)! }
let n = nm[0]
let m = nm[1]
let num = readLine()!.split(separator: " ").map { Int($0)! }.sorted()
var output = Array(repeating: 0, count: m)

func backtrack(_ index: Int) {
    if index == m {
        print(output.map { String($0) }.joined(separator: " "))
        return
    }
    
    var used = Set<Int>() // 똑같은 조합을 체크하기 위한 집합
    
    for i in 0..<n {
        // 같은 수 여러번 골라도 되니까 방문처리는 안해도 됨
        if !used.contains(num[i]) { // 이미 포함하고 있는 조합이면 조건문 충족X
            output[index] = num[i]
            used.insert(num[i])
            backtrack(index+1)
        }
    }
}

backtrack(0)

기존과 다르게 output이라는 정수 배열을 만들고, index에 값을 할당해주는 방식으로 풀었다.

9번 문제와 다르게 같은 수를 여러번 써도 되니까 visited 방문 처리는 해줄 필요가 없고, 

대신 이미 기존에 있는 조합이라면 used 집합을 통해 체크해주는 방식

 

 

---

조건에 비내림차순이 추가됐다. 쉽게 생각했는데 코드 이해를 제대로 못해서 그런건지 약간 고민을 했다... 바보시키.;

import Foundation

/*
 같은 수 여러번 골라도 되고,
 비내림차순!
 */

let nm = readLine()!.split(separator: " ").map { Int($0)! }
let n = nm[0]
let m = nm[1]
let num = readLine()!.split(separator: " ").map { Int($0)! }.sorted()
var output = Array(repeating: 0, count: m)

func backtrack(_ index: Int) {
    if index == m {
            print(output.map { String($0) }.joined(separator: " "))
        return
    }
    
    var used = Set<Int>() // 똑같은 조합을 체크하기 위한 집합
    
    for i in 0..<n {
        // 같은 수 여러번 골라도 되니까 방문처리는 안해도 됨
        if index-1 >= 0 {
            // 이미 포함하고 있는 조합이면 조건문 충족X
            /* 현재추가하는 수 = num[i] 즉, output[index]에 들어갈 수가 output[index-1]보다 더 커야 한다. 그게 비내림차순!
             */
            if !used.contains(num[i]) && output[index-1] <= num[i] {
                output[index] = num[i]
                used.insert(num[i])
                backtrack(index+1)
            }
        } else {
            if !used.contains(num[i]) && output[0] <= num[i] {
                output[index] = num[i]
                used.insert(num[i])
                backtrack(index+1)
            }
        }
    }
}

backtrack(0)

현재 추가하는 수 = num[i]

즉, output[index]에 들어갈 수가 output[index-1]보다 더 커야 한다. 그게 비내림차순!

코드 좀 비효율적으로 반복했는데.. 일단 맞았따. 우선 직관적이니까......

 

---

1182 부분수열의 합

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

 

처음에 생각한 방식은 아래와 같다. n과 m 시리즈를 쭉 풀어서 잘 풀 수 있을 거란 자신감과 다르게 어려웠다... ; 시앙..

조합이고, 경우의 수를 구하는 거고,
재귀탈출 = 결과배열의 합이 s랑 같을 때 탈출
한정조건 = 이미 갖고 있는 것은 포함하면 X && 비내림차순이어야 해 

 

 

내가 생각한 한정조건에서 놓친 것은, 크기가 양수인 부분수열이라는 점 -> 그래서 depth > 0 이라는 조건을 추가해야 했다.

나는 처음에 푼 방식은 아래와 같다. 시간초과가 났는데. n이 20이라는 점에서 그럴만도..

import Foundation

/*
N개의 정수들 중에서 부분수열을 뽑아서 그걸 합한 값이 S가 되는 경우의 수
 */
let ns = readLine()!.split(separator: " ").map { Int($0)! }
let n = ns[0]
let s = ns[1]
let num = readLine()!.split(separator: " ").map { Int($0)! }.sorted()

var calculateList = [Int]()
var sum = [Int]()
var visited = Array(repeating: false, count: n)

var result = 0 // 경우의 수
 
// 조합이고, 경우의 수를 구하는 거고,
// 재귀탈출 = 결과배열의 합이 s랑 같을 때 탈출
// 한정조건 = 이미 갖고 있는 것은 포함하면 X && 비내림차순이어야 해
func backtrack() {
    if sum.reduce(0, +) == s {
        result += 1
        return
    }
    
    
    for i in 0..<n {
        if sum.count-1 >= 0 {
            if sum[sum.count-1] <= num[i] && !visited[i] {
                visited[i] = true
                sum.append(num[i])
                backtrack()
                sum.removeLast()
                visited[i] = false
            }
        } else {
            if !visited[i] {
                visited[i] = true
                sum.append(num[i])
                backtrack()
                sum.removeLast()
                visited[i] = false
            }
        }
        
    }
}

backtrack()
print(result)

 

도저히 안풀려서 답지를 참고했다.

1. 방문처리 배열을 사용해서 이미 선택한 원소를 다시 선택하지 않도록 처리하는 것보다는
startIndex 파라미터를 사용해서 이전에 선택한 원소 이후부터 탐색하도록 구현하는 것이 더 간단하고 효율적

2. depth는 현재까지 선택된 원소의 개수를 나타내는 변수, 

재귀호출이 진행될수록 원소의 개수가 증가하고, 이게 부분수열의 길이를 나타냄
depth > 0 즉, 최소 하나 이상의 원소를 선택 시에만 경우의 수가 증가

 

3. sumArray를 사용해서 현재 선택된 부분수열을 저장하는 것보다는
sum 변수를 통해서 현재까지의 부분수열의 합을 저장하는 것이더 간단하고 효율적

 

다른 방식으로 푼 풀이들도 있는데 이해가 와닿지는 않지만 더 좋은 풀이로 판단된다.

현재 내 인덱스에 해당하는 값을 더해주느냐, 아니면 더하지 않느냐 이 두 가지의 경우를 고려해서 재귀를 도는 부분이 있다.

 

<정답풀이>

즉, 재귀호출 시

-> backtracking마다 이전에 선택한 원소 이후부터 탐색하고, (startIndex +1) 

-> depth+1 : 선택되는 원소의 개수가 하나씩 증가한다. 즉, 부분수열의 길이가 증가한다.

import Foundation


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

var sum = 0
var count = 0 // 경우의 수

func backtrack(_ startIndex: Int, _ depth: Int) {
    if sum == s && depth > 0 {
        count += 1
    }
    
    for i in startIndex..<n {
        sum += num[i]
        backtrack(i+1, i+1)
        sum -= num[i]
    }
}

backtrack(0, 0)
print(count)