백준 알고리즘 2231번 분해합 (C언어)

브론즈Ⅱ

 

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

2231번: 분해합

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	192 MB	121035	55647	43736	45.290%

 

문제

어떤 자연수 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을 출력한다.

예제 입력 1

216

예제 출력 1

198

 

풀이 방법

반응형

분해합 문제는 자연수 N이 주어졌을 때 N의 가장 작은 생성자를 구하는 문제입니다.

 

이 문제의 경우 1부터 n-1까지의 수의 분해합을 하나씩 구하고 입력한 자연수 N과 비교해본 후 자연수 N과 같으면 그 분해합의 생성자를 출력, 같지 않다면 0을 출력하면 됩니다.

 

내 코드

#pragma warning(disable:4996)
#include <stdio.h>
 
int main() {
 
    int n, n2, tmp, sum, result = 0;
 
    scanf("%d", &n);
 
    for (int i = 1; i < n; i++) {
        n2 = i, sum = i;
        while (n2 != 0) {
            tmp = n2 % 10;
            sum += tmp;
            n2 /= 10;
        }
        if (n == sum) {
            result = i;
            break;
        }
    }
    printf("%d\n", result);
 
    return 0;
}

sum의 값을 구하는 코드부분 입니다. 

먼저 sum에 생성자인 i의 값을 넣고, 생성자인 i의 값을 변경할 수는 없기 때문에 n2라는 변수를 만들어 i를 대입합니다. 이후 while문을 돌며 n2의 첫번째 자리에 있는 값을 sum에 대입합니다. 마지막으로 n2에 n2를 10으로 나눈 몫을 곱한 후 대입해주어 다음 자릿수의 값을 이후에 sum에 넣을 수 있도록 해줍니다.