[BOJ-9506][C++] 약수들의 합

문제

어떤 숫자 n이 자신을 제외한 모든 약수들의 합과 같으면, 그 수를 완전수라고 한다.

예를 들어 6은 6 = 1 + 2 + 3 으로 완전수이다.

n이 완전수인지 아닌지 판단해주는 프로그램을 작성하라.

 

입력

입력은 테스트 케이스마다 한 줄 간격으로 n이 주어진다. (2 < n < 100,000)

입력의 마지막엔 -1이 주어진다.

 

출력

테스트케이스 마다 한줄에 하나씩 출력해야 한다.

n이 완전수라면, n을 n이 아닌 약수들의 합으로 나타내어 출력한다(예제 출력 참고).

이때, 약수들은 오름차순으로 나열해야 한다.

n이 완전수가 아니라면 n is NOT perfect. 를 출력한다.

 

예제 입력 1 

6
12
28
-1

 

예제 출력 1

6 = 1 + 2 + 3
12 is NOT perfect.
28 = 1 + 2 + 4 + 7 + 14

 

출처

ICPC > Regionals > North America > Pacific Northwest Regional > 2013 Pacific Northwest Region Programming Contest F번

 

알고리즘 분류

• 수학
• 구현
• 정수론

 

문제 출처

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

9506번: 약수들의 합

 

---

 

문제 해결 방법

• [단계별로 풀어보기] 문제집에 새로 추가된 문제이다.
• 완전수의 개념을 이해하고, 조건에 맞게 구현하면 되는 쉬운 문제였다.

 

코드

#include <iostream>
#include <vector>
using namespace std;

int n;

void Solution(int n) {
    int sum;
    vector<int> divisors;

    sum = 0;
    for (int num = 1; num < n; num++) {
        if (n % num == 0) {
            divisors.push_back(num);
            sum += num;
        }
    }

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

void Solve() {
    while (true) {
        cin >> n;

        if (n == -1) {
            break;
        }
        Solution(n);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Solve();

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [약수, 배수와 소수]
• 브론즈I