[백준/C언어] 2231번 - 분해합

백준 웹사이트 "2231번 - 분해합" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

2231번: 분해합

---

소스 코드

#include <stdio.h>

// 1. 입력된 수의 분해합을 구하는 프로그램을 작성한다.
int find_dn(int n);

int main(void){
    int N;
    scanf("%d", &N);

// 2. N 이하 모든 수의 분해합을 계산 및 비교한다.
    for(int i=1; i<=N; i++){
        if(find_dn(i) == N){
            printf("%d\n", i);
            break;
        }
        if(i==N)
            printf("0");
    }
}

int find_dn(int n){
    int dn = n;
    while(n>0){
        dn = dn + n%10;
        n = n/10;
    }
    return dn;
}

---

문제 풀이

  이전 문제 중에서 '생성자'에 대해 다루는 문제가 있었습니다. 백준 "4673번 - 셀프 넘버" 문제는 분해합을 계산하는 함수를 작성한 뒤, 이용하는 문제였습니다. 이 문제에서도 그때의 코드를 참고하여, 분해합을 계산하는 함수 'find_dn'을 이용해줍니다.

  브루트 포스 알고리즘을 어떻게 이용할 수 있을까요? N이 주어지면, N보다 작은 모든 수에 대해 'find_dn'을 적용하여 생성자를 찾을 수 있습니다. 분해합의 정의가 주어진 수와 그 수의 각 자릿수의 합이므로, 어떤 수의 생성자는 그 수보다 클 수 없습니다 (1의 경우도, 주어진 수(1)와 그 수의 각 자릿수(1)의 합은 2입니다). 따라서 브루트 포스 알고리즘으로, N 이하 모든 수의 분해합을 계산 및 비교합니다. 도중에 N의 생성자가 발견되면 이를 출력하고 for문을 종료하며, 끝까지 발견되지 않는다면 0을 출력합니다.

  아래는 백준 웹사이트 "4673번 - 셀프 넘버" 문제풀이 링크입니다. 4673번 역시 브루트 포스 알고리즘을 이용하는 문제이므로, 만약 풀어보지 않으셨다면 풀어보는 것을 추천합니다!

[백준/C언어] 4673번 - 셀프 넘버