[완전 탐색] 백준 브론즈2 2231번: 분해합(Swift)

https://www.acmicpc.net/problem/2231

2231번: 분해합

풀이과정

분해합 문제의 경우 특정수 N에 대하여 생성자를 찾는 문제이다.

생성자 M은 [ M + M의 각 자릿수의 합 = N ] 위 조건을 만족하는 가장 작은 수이다.

위 문제의 경우 1부터 주어진 수 N까지 반복문을 통해 하나씩 대입해도 312ms 시간으로 통과한다.
하지만, 그것이 문제 출제의도는 아닌 것 같아 조건을 통해 시간을 단축시켜 보자.

위에서 언급했듯 생성자 M은 [ M + M의 각 자릿수의 합 = N ] 위 조건을 만족해야 한다.

그럼 식을 [ M = N - M의 각 자릿수의 합 ] 위와 같이 바꿔줄 수 있다. 여기서 M이 3자리 수라 가정했을 때 "M의 각 자릿수의 합"의 최댓값은 9 + 9 + 9로 27이다.

즉, 자릿수 * 9가 "M의 각 자릿수의 합"에 올 수 있는 최댓값이 된다.

그럼 그 뜻은 세 자리 수의 M은 N - 27보다 크고 N보단 작다.

하지만, N이 18 이상부터 위 조건이 가능하기에 18이하 면 1부터 탐색한다.

Code

let n = readLine()!
let num = Int(n)!
var sum = 0
var m = 0
var start = 1

if num > 18 { startN = num - n.count * 9 }

for i in start..<num {
  sum = i
  for j in String(i) {
    sum += Int(String(j))!
  }
  
  if sum == num {
    m = i
    break
  }
}

print(m)