숫자 만들기

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

• 완전탐색으로 문제를 해결할 경우 O(N^2)만 되더라도 N이 100,000이기 때문에 시간안에 해결하는 것이 불가능함
• 따라서, 다른 문제 해결 방법을 설계 해야 하는데, 위 문제에서 끝에 1이 더해지는 경우, 2가 더해지는 경우 3이 더해지는 경우를 생각해 보면 N = 4일 때, 3을 만드는 경우 각각에 + 1을 해주면 4가 되고, 2를 만드는 경우에 각각 + 2를 해주면 4가 되고, 1을 만드는 경우에 + 3을 해준 후 위 경우의 수를 모두 더하게 되면 4를 만드는 경우의 수를 구할 수 있음
• 즉, "나"를 구하기 위해 작은 "나"를 이용하는 패턴으로 동적 계획법을 사용하여 문제를 해결할 수 있음
• T[i] = 1, 2, 3의 합으로 i를 만들 수 있는 경우의 수, T[1] = 1, T[2] = 2, T[3] = 4가 기저조건이고,
• T[4] 부터는 앞의 3개의 소문제의 합을 통해 자신을 구할 수 있으므로 O(N)의 시간복잡도로 문제를 해결할 수 있음

5. 전체 코드

//MARK: - 숫자 만들기

//MARK: - Framework
import Foundation

//MARK: - Function
func solution() -> Void {
    //MARK: - Input
    guard let N: Int = Int(readLine() ?? "0") else { return }
    let baseCondition: Int = 3
    var sum: Int = 0
    var table: [Int] = Array(repeating: 0, count: N + 10)
    
    //MARK: - Process
    //1. 부분 문제를 정의
    //T[i] = 1, 2, 3을 사용하여 i을 만드는 총 경우의 수
    //같은 숫자를 중복하여 사용할 수 있음
    
    //2. 점화식을 세운다.
    //T[0] = 불가능
    //T[1] = 1, T[2] = T[1] + 1, T[3] = T[2] + T[1] + 1 -> Base Condition
    //T[4] = T[3] + T[2] + T[1]
    //T[i] = T[i - 3] + T[i - 2] + T[i - 1]
    table[1] = 1
    for i in 2...baseCondition {
        sum += table[i - 1]
        table[i] = sum + 1
    }
    
    for i in stride(from: baseCondition + 1, through: N, by: 1) {
        table[i] = (table[i - 3] + table[i - 2] + table[i - 1]) % 1000007
    }
    
    //MARK: - Output
    print(table[N])
}
solution()

 

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