division

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

1. n - 1 부터 정수를 하나하나 놓아봄으로써, 그 합이 n이 되도록 결정하는 구조이므로
2. 재귀함수를 통한 Back-tracking 알고리즘으로 문제를 해결할 수 있음
3. 큰 수부터 결정되어야 하므로 큰 수(n - 1)부터 차례차례 놓으면서 현재 놓아야하는 숫자가 이전 숫자보다 큰 경우는 제외시킴으로써 문제를 해결할 수 있음
4. 현재 숫자의 합이 n이 되는 경우가 기저조건이 됨

5. 전체 코드

 

//MARK: - division

//MARK: - Framework
import Foundation

//MARK: - Variable
var count: Int = 0

//MARK: - Function
func getDivision(_ currentSum: Int, _ current: Int, _ n: Int, _ result: inout [Int]) -> Void {
    if currentSum == n {
        var answer: String = ""
        for i in 0..<current - 1 {
            answer += "\(result[i])+"
        }
        answer += "\(result[current - 1])"
        print(answer)
        count += 1
    } else {
        let currentNumber: Int = current == 0 ? n - 1 : n - currentSum
        for i in stride(from: currentNumber, through: 1, by: -1) {
            if current > 0 && result[current - 1] < i {
                continue
            }
            result[current] = i
            getDivision(currentSum + i, current + 1, n, &result)
        }
    }
}

func solution() -> Void {
    //MARK: - Input
    guard let n: Int = Int(readLine() ?? "0") else { return }
    var result: [Int] = Array(repeating: 0, count: n + 10)
    
    //MARK: - Process & Output
    getDivision(0, 0, n, &result)
    print(count)
}
solution()

 

전체코드는 여기에서 확인할 수 있습니다.