[BOJ] 2231. 분해합 (C,Python3)

• 코딩 초보. 구현을 목표로 하였기에 비효율적일 수 있습니다.

---

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을 출력한다.

 

---

1.Python

 

n=int(input())

for i in range(1,n+1):
    k=n-i
    chk=0
    a=i
    while(a!=0):
        b=a%10 
        chk+=b
        a=a//10 
    if (chk==k):
        print(i)
        break
    if (i==n and chk!=k):
        print(0)
        break

모든 경우의 수를 찾아 하나하나 조건에 맞는지 판별하는 브루트포스 알고리즘이다. 이번에는 c언어가 아니라 파이썬으로 먼저 구현을 시도해보았다.  

가장 작은 값을 구해내야하므로 for반복문을 이용하여 1부터 검토를 하도록 하였다. 만약에 216이라는 수가 입력된다면 (1,215) (2,214) (3,213)... 으로 경우의 수를 차례대로 구해 하나씩 각 자리 수의 합이 같은지를 판단해야 한다. 

 

처음에는 3자리 수일때, 2자리 수일때를 각각 if조건문을 통해 분리해주려고 했지만.. 입력되는 수가 7자리까지이므로 너무 비효율적일것 같아 이번에는 while문을 사용했다. (ex. 만약, i값이 123이라면, a=123, b=123%10=3 ,chk=3 a는 다시 12, b= 12%10 = 2 ,chk=3+2=5, ... 이런식으로 반복하도록 하여 a 값이 0이면 while 반복문을 빠져나오도록 하였다. 그렇게 각 자리수를 더한 값이 저장된 chk 변수가 k 값과 같으면 print(i)를 하도록 하고, 만약에 for 반복문을 거의 다 돌았는데도 chk 가 k값과 같이 않으면 0을 출력하도록 했다. 

 

※주의할 점! for 반복문에서 범위를 1~n+1 로 해주어야한다. 만약에 그냥 n으로만 해놓으면 n-1까지만 검토를 한다. 답이 n일 경우도 있으니 모두 검토할 수 있도록 범위 설정에 유의할 것. 

---

2.C99

 

#include <stdio.h>

main() {
	int n,k,chk,a,b;
	scanf("%d", &n);

	for (int i = 1; i < n + 1; i++) {
		k = n - i;
		chk = 0;
		a = i; 
		while (a != 0) {
			b = a % 10;
			chk += b;
			a = a / 10;
		}
		if (chk == k) {
			printf("%d",i);
			return 0; 
		}
		if (i == n && chk != k) {
			printf("0");
			return 0; 
		}
	}
}

같은 방식으로 구현하면 된다. 구현에 큰 차이는 없다.