문제 정보

백준 ( BOJ ) 2231 분해합

문제 풀이 : 시뮬레이션

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

시작 Thinking

이걸 가장 작은 값을 찾으려면 0부터 해야할까?

라는 생각으로 시작 해 주시면 됩니다.

다른분들 풀이를 보니 0에서 시작해도 되긴 하더라구요.

그래도 우리는 더 극한의 상황에 대비해야 합니다.

그렇다면 탐색을 어디서부터 시작 해야 할 까요?

N의 값은 1 이상 100만 이하입니다.

정답도 당연히 100만 이하가 되겠죠.

그럼, N 이 주어졌을때 정답과의 최대 차이는 몇일까? 에서 시작 해 보도록 합시다.

N = 정답 + 정답의 각 자릿수의 합

이 공식이 됩니다.

그렇다면 N - 정답의 각 자릿수의 합 = 정답

이라는 이야기도 하죠.

정답의 각 자릿수의 합의 최대치는 몇일까요?

당연히 9로 도배된 수가 가장 큰 자릿수의 합이 될 겁니다.

정답이 될 순 없지만

999,999 이값의 각 자릿수의 합은

9*6 = 54 입니다.

즉, 100만 이하의 숫자에서 어떤 각 자리숫자의 합도 54를 넘지 못한다는겁니다.

여기까지 오시면 눈치 채셨을 거라고 생각합니다.

N에서 54를 빼고, 그 부분부터 탐색을 시작 해 주면 됩니다.

코드

#include <iostream>


using namespace std;


int n;
int temp;

bool cal() {
	int compare = temp;
	int temptemp = temp;
	while (temptemp > 0) {
		compare += temptemp % 10;
		temptemp /= 10;
	}
	if (compare == n)
		return true;
	else
		return false;
}

int main() {
	cin >> n; 
	int result = 0;
	int results = 0;
	if (n > 54)
		temp = n - 54;
	else
		temp = 0;

	while (temp < n) {
		if (cal() == true) {
			result = temp;
			break;
		}
		temp++;
	}

	cout << result;
	

}