백준 9506 약수들의 합 (c+++) : 피너클

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

 

수학문제다.

int n;
bool b[50001];
int arr[50001];
int len;

n은 입력받는 숫자이고

b는 약수인지 아닌지 기록하는 bool배열

arr은 약수가 담기는 배열, len은 arr의 길이다.

	while (true) {
		cin >> n;
		if (n == -1) break;

		for (int i = 2; i <= 50000; i++) b[i] = false;
		int sum = 0;
		len = 0;

미리 세팅을 해둔다.

for (int i = 2; i <= n / 2; i++) {
	if (n % i == 0 && !b[i]) {

		b[i] = true;
		b[n / i] = true;

		arr[len] = i;
		arr[len + 1] = n / i;
		len += 2;
		
		sum = sum + i + n / i;
	}
}

n/2까지만 반복문을 돌리며 만약 n이 i로 완전히 나누어떨어지고 약수로 체크가 되지 않았다면

i와 n를 i로 나눈 수를 기록해주고 arr에 둘다 기록해준뒤 sum에 더해준다.

arr[len] = 1;
len += 1;
sort(arr, arr + len);

반복문에서 나오면 배열에 1을 추가해준뒤 정렬해준다.

if (sum + 1 == n) {
	cout << n << " = ";
	for (int i = 0; i < len - 1; i++) {
		cout << arr[i] << " + ";
	}
	cout << arr[len - 1] << '\n';
}
else {
	cout << n << " is NOT perfect." << '\n';
}

sum에다가 1을 더하는 이유는 for반복문에서 1는 고려되지 않았기 때문이다.

각자에 맞게 출력하면 된다.

#include <iostream>
#include <algorithm>

using namespace std;

int n;
bool b[50001];
int arr[50001];
int len;

int main()
{
	while (true) {
		cin >> n;
		if (n == -1) break;

		for (int i = 2; i <= 50000; i++) b[i] = false;
		int sum = 0;
		len = 0;

		for (int i = 2; i <= n / 2; i++) {
			if (n % i == 0 && !b[i]) {

				b[i] = true;
				b[n / i] = true;

				arr[len] = i;
				arr[len + 1] = n / i;
				len += 2;
				
				sum = sum + i + n / i;
			}
		}
		arr[len] = 1;
		len += 1;
		sort(arr, arr + len);

		if (sum + 1 == n) {
			cout << n << " = ";
			for (int i = 0; i < len - 1; i++) {
				cout << arr[i] << " + ";
			}
			cout << arr[len - 1] << '\n';
		}
		else {
			cout << n << " is NOT perfect." << '\n';
		}
	}
}

전체코드다.