[백준][c/c++] 2231번: 분해합

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

2231번: 분해합

문제

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

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define INF 2147000000

int a[1000100] = { 0 };

int main() {
    int n;
    int target;
    int min = INF;
    int digit = 10;
    int i, j;

    scanf("%d", &n);
    //  a 배열에 자신의 인덱스의 생성자를 저장
    for (i = 1; i <= n; i++) {        
        digit = 10;
        a[i] += i;
        a[i] += i % digit;  //  일의 자리 더함

        while (i / digit != 0) {    //  십의 자리 ~~~ 더함
            a[i] += i % (digit * 10) / digit;
            digit *= 10;
        }
    }
    
    /*
    생성자를 역추적할 때. 이 문제의 조건과는 다름

    target = n;     //  생성자를 거슬러 올라가기 위해서 target 설정

    for (i = n; i >= 1; i--) {
        if (a[i] == target) {
            target = i;
        }
    }
    */
    
    //  생성자들을 찾으면서, 그 중 최솟값을 구함
    for (i = n; i >= 1; i--) {
        if (a[i] == n) {
            if(i < min) {
                min = i;
            }
        }
    }
    
    
    if (min == INF) {   //  생성자가 없을 때
        printf("0\n");
    }
    else {
        printf("%d\n", min);
    }
}

 

생성자를 역추적하는 코드는 주석처리를 해놓았습니다. (n부터 순차적으로 작아지면서)

ex) n = 216 일 때: 216 -> 207 -> 189 -> 180 -> 171 -> ~~~~~~~ -> 108

이 코드의 주석을 풀고 target을 출력하면 생성자를 거슬러 올라가서 가장 작은 생성자를 출력합니다.

(이 문제의 조건과는 맞지않습니다. 처음에 문제의 의도가 헷갈려서 ..... )

 

 

이 코드에서는

a 배열에다가 자신의 index에 해당하는 숫자의 분해합을 미리 저장해놓았습니다.

그리고 그 분해합과 index의 연산을 통해서 

생성자들의 최솟값을 찾습니다.

 

마지막 출력부분에서는 min이 건드려지지 않아서 INF를 그대로 보존하고 있을 때 0 을 출력하도록

예외케이스를 분리하였습니다.