[백준] 2231번 분해합 [Swift]

문제 링크

2231번: 분해합

문제

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자릿수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.

문제 풀이

이 문제를 풀이하는데 가장 중요한 것은 정수를 자리수별로 더하는 방법인 것 같습니다.

저는 이런 방법을 사용했습니다.

예를 들어 156이라는 숫자가 있을 때, 우선 156을 10으로 나눈 수를 구합니다.

6이 되겠죠?

그런 뒤 156을 10으로 나는 몫을 구합니다.

즉 15를 구하게됩니다.

15를 다시 10으로 나눈 수를 구하면 5가 됩니다.

그런 뒤 15를 10으로 나눈 몫 1을 구하고, 이를 다시 10으로 나눈 수를 구하면 1이 됩니다.

이런 방법으로 정수를 각 자릿수 별로 나눌 수 있었습니다.

 

이 문제에서 구하는 것은 분해합이라는 녀석 중 가장 작은 값을 찾는 것입니다.

가장 작은 것부터 찾으면 되니까 그냥 1부터 입력받은 수인 N까지 모두 구하는 방법을 택했습니다.

이렇게 무식하게 찾아도 시간 복잡도에 무리가 가지 않는 이유는 N의 최댓값이 100만이기 때문입니다.

 

그리고 만약 분해합을 찾지 못할 경우 0을 출력하는 것을 주의하여 문제를 풀면 됩니다!

소스 코드

func solution() -> Int {
    let n = Int(String(readLine()!))!
    var result: Int = 1
    
    for i in 1..<n {
        var temp = i
        result = i
        if i >= 1 && i < 10 {
            result = 2 * i
            if result == n {
                return i
            }
        } else {
            while (temp != 0){
                result += temp % 10
                temp /= 10
            }
            if result == n {
                return i
            }
        }
    }
    return 0
}

print(solution())