BOJ 2231 분해합

문제출처 : https://www.acmicpc.net/problem/2231

1. 문제요약

- 어떤 자연수 M => 세 자릿수 라면 100a + 10b + c => M + a + b + c = N 즉, M과 각 자릿수의 합을 분해합, M을 생성자, N을 분해합

- 1 <= N <= 1,000,000 인 자연수 N이 주어 졌을 때 가장 작은 생성자는?

2. 접근방법

- 생성자는 분해합을 넘을 수 없으므로 1 부터 N-1 까지의 모든 수를 다 해보자

- 좀 더 생각해보면 분해합 N이 만들어 질 수 있는 생성자의 최대 자릿수는 6자릿수

  (생성자가 1,000,000 이면 분해합은 1,000,001 이므로 7 자릿수는 나올 수 없음)

  각 자릿수의 최대 값은 9

  즉, 생성자는 분해합 보다 54 이상 작을 수 없음.

  N-54 부터 N-1 까지만 찾으면 됨.

  가장 작은 수 부터 찾을 거니 처음 만나는 생성자가 최소값

3. 시간복잡도

- 두 가지 경우 모두 N

- 당연히 실제 시간은 전체 검색시 8ms / 55개 검사시 0ms

4. 회고

- 처음엔 다 했는데...

- 다른 사람의 소스 코드를 보고 깨달음

- 각 자릿수 합의 최대 범위

소스코드

#include<iostream>
using namespace std;

int main(void){
	int n;
	cin >> n;
	for (int i = n - 54; i < n; i++){
		int temp = i, sum = i;
		while (temp){
			sum += temp % 10;
			temp /= 10;
		}

		if (sum == n){
			cout << i << "\n";
			return 0;
		}
	}
	cout << '0' << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]