[백준/BOJ] 9506번 약수들의 합 (C/C++)

백준 온라인 저지(BOJ) 9506번 약수들의 합
https://www.acmicpc.net/problem/9506

9506번: 약수들의 합

* 사용언어 : C언어, C++

 

1. 문제

어떤 숫자 n이 자신을 제외한 모든 약수들의 합과 같으면, 그 수를 완전수라 함
n 이 완전수이면 모든 약수를 출력, 아니면 n is NOT perfect. 를 출력

 

2. 풀이

최대한 심플하게 코딩을 하고 싶었는데
문제 조건이 까다로워서 복잡하게 구현할 수 밖에 없었습니다.
 
가장 먼저 1 부터 n 까지 n 의 약수인지 아닌지를 판단하는 for 문을 작성했습니다.
약수인지 여부는 n % i == 0 으로 확인할 수 있습니다.
 
약수 여부를 확인하면서 동시에 출력까지 할까 했는데
아닌 경우 출력 방식이 달라서 불가했습니다.
따라서 배열에 기록을 했습니다. (n % i 를 i 번 자리에 기록)
 
약수 여부를 판단하면서 sum 이라는 변수에 약수들의 합을 미리 더해두었습니다.
그리고 이 값이 n 보다 커지면 이미 완전수가 아니므로
for 문을 탈출하게 구현했습니다.
 
이후 2번째 for 문에서 sum 이 n 과 같은지를 확인한 후 다른 방식으로 출력하게 했습니다.
완전수인 경우에는 마지막에 + 를 출력하면 안되기 때문에
기존에 선언해둔 sum 을 재활용하여 총합을 기록했고,
출력한 내용이 끝나면 enter(\n) 를 출력하며 마치도록 구현했습니다.
 
이하 설명은 아래 소스 코드로 대체하겠습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
9506_약수들의 합
1504KB	0ms
*/
#include <cstdio>

int arr[100001], n, sum;

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	while (1) {
		scanf("%d", &n);
		if (n == -1) break;

		sum = 0;
		for (int i = 1; i < n; ++i) {
			arr[i] = n % i;
			if (!arr[i]) sum += i;
			if (sum > n) break;
		}

		if (sum == n) {
			sum = 0;
			printf("%d = ", n);
			for (int i = 1; i < n; ++i) {
				if (!arr[i]) {
					printf("%d ", i);
					sum += i;
					if (sum == n) {
						printf("\n");
						break;
					}
					printf("+ ");
				}
			}
		}
		else {
			printf("%d is NOT perfect.\n", n);
		}
	}
	return 0;
}