[C++] BOJ 9506번: 약수들의 합

학교에서 진행하는 수업에서 같이 듣는 팀원이 공유한 알고리즘 문제를 풀어보았다. 문제의 난이도는 브론즈 1으로, 빠르게 풀 수 있을 거라 생각했지만 출력을 적절하게 하도록 코드를 작성하는 데에 예상보다 시간이 걸렸다.

문제 링크

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

문제 분석

해당 문제는 완전수를 찾는 문제이다. 완전수란 자기 자신을 제외한 모든 약수를 더했을 때 자기 자신과 같은 값이 나오는 수를 의미한다. n이 완전수가 아님이 판별되면 n is NOT perfect.를 출력한다. n이 완전수일 경우 n을 약수들의 합으로 표현해야 하는데, 이 부분에서 코드가 길어졌다.

문제 풀이

먼저 주어진 숫자 n의 약수를 구하는 법을 판단해보자. 어떤 수 k가 있을 때, n % k == 0이라면 k는 n의 약수이다.

이에 따라 n 자기 자신을 제외한 n의 모든 약수를 처리하는 코드는 다음과 같아진다.

for(int i=1; i<n; i++)
    if(n % i == 0) // i는 n의 약수일 경우

위의 if문 내에서 약수 i를 처리하면 된다.

n이 완전수일 경우 출력이 6 = 1 + 2 + 3과 같은 형태로 출력되어야 하므로 n의 약수를 담아둘 배열이 필요하다. 따라서 아래와 같이 배열을 선언한다.

int factors[100000] = {
    0,
};
int factor_size = 0;

배열 factors의 크기가 100000인 이유는 문제에서 n의 최대값이 100000이 될 수 없다고 나와 있기 때문이다. factor_size는 factors 배열에 담긴 약수의 갯수를 저장하는 변수이다.

int sum = 0;
for (int i = 1; i < n; i++)
{
    if (n % i == 0)
    {
        sum += i;
        factors[factor_size++] = i;
    }
}

위 코드는 해당 수가 완전수인지 비교하기 위해 약수의 값을 모두 더하고, 약수들을 factors 배열에 저장해두는 코드이다. 만약 계산 결과 sum == n이면 완전수에 해당하며, sum != n이면 n이 완전수가 아니다.

먼저 sum != n인 경우 아래와 같은 코드로 결과를 출력한다.

cout << n << " is NOT perfect." << '\n';

그리고 sum == n인 경우 factors 배열에 저장한 약수들을 이용해 결과를 출력한다.

cout << n << " = ";
for (int i = 0; i < factor_size; i++)
{
    cout << factors[i];
    if (i != factor_size - 1)
        cout << " + ";
}
cout << '\n';

전체 코드

위의 코드를 종합해 작성한 전체 코드는 다음과 같다.

#include <iostream>
#include <vector>

using namespace std;

void solution(int n)
{
    int sum = 0;
    int factors[100000] = {
        0,
    };
    int factor_size = 0;

    for (int i = 1; i < n; i++)
    {
        if (n % i == 0)
        {
            sum += i;
            factors[factor_size++] = i;
        }
    }

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

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;

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

    return 0;
}

 

결과