백준 2231번 - 분해합 문제 C++

오늘 백준 문제를 풀다가 너무너무 똑똑한 풀이법이 있어서 기록한다. 

 

📍 백준 2231번 문제 - 분해합 이다. 

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

 

🧩 문제 요약 

어떤 자연수 N이 있을 떄, 

• 어떤 수 M이 M+각 자리수의 합 = N이 되면 M 은 N의 생성자라고 한다. 
• N의 가장 작은 생성자를 출력하는 문제다. --- 없으면 0 출력 

예:
N = 216 → 198 + 1 + 9 + 8 = 216 → 198이 생성자

 

 

🧾 내가 작성한 코드 

#include <stdio.h>
using namespace std;


int main(){
    int N; 
    scanf("%d", &N); // 값 입력

    for(int i=1;i<N; i++){  // 최소값 생성자 구하기 
        int answer = 0, tmp = i;
        answer += i; 
        while(tmp!=0){
            answer += tmp%10;
            tmp = tmp/10;
        }
        if(answer == N) {
            printf("%d\n", i); 
            return 0;
        }
    }
    printf("%d",0); // 생성자가 없으면 0 
}

 

 

🧾 상위 코드 

#include<stdio.h>
int main(){
    int N, i, j, k;

    // 입력받고, i = N - 60 부터 시작
    for(scanf("%d", &N), i = N - 60; k - N && i < N; i++) 
        // j = i, k = i 에서 각 자리수 더함
        for(k = j = i; j; j /= 10) 
            k += j % 10;

    // k == N이면 생성자 찾은 것, 아니면 0 출력
    printf("%d", k - N ? 0 : i - 1);
}

 

 

👍 이 코드에서 배울점 

• for문의 초기식은 ' , ' 연산자를 사용해 다양한 조건을 붙일 수 있다. 
• 왜 N - 60 부터 시작? 
  • N은 문제 요구조건에 따라 최대 1000,000이다.
  • 어떤 수의 생성자는 최대 자기 자리수 합만큼 작을 수 있다. 
  • 999,999같은 경우, 6자리 수니까 최대 자리수합은 9*6 = 54이다. 
  • ✅그래서 넉넉하게 N-60부터 시작하면 안전하다.