[BOJ 백준] 2247번 : 실질적 약수 (C++)

[BOJ 백준] 2247번 : 실질적 약수 (C++)

목차

• 01. 개요
• 02. 접근 방식
• 03. 정답 코드

---

01. 개요

출처

https://solved.ac/profile/free4760

 

문제

 

입력

 

출력

 

예시

 

 

---

02. 접근 방식

 

요약

1. n에 대해서 2~n/2까지 나눠서 약수의 개수를 구하기

2. 구한 개수를 바탕으로 모두 더하기

 

과정

위 요약 과정을 1부터 20까지의 1과 자기 자신을 제외한 약수를 모두 구해보겠습니다.

1    0
2    0
3    0
4    2
5    0
6    2,3
7    0
8    2,4
9    3
10   2,5
11   0
12   2,3,4,6
13   0
14   2,7
15   3,5
16   2,4,8
17   0
18   2,3,6,9
19   0
20   2,4,5,10

 

 

1~20까지 중 2를 실질적 약수로 사용하는 경우는 9개입니다.

3을 실질적 약수로 사용하는 경우는 5개입니다.

이를 10(n/2)까지 확인하면, 아래와 같습니다.

20 / 2 = 10 -> 2*(10-1)
20 / 3 = 6 -> 3*(6-1)
20 / 4 = 5 -> 4*(5-1)
20 / 5 = 4 -> 5*(4-1)
20 / 6 = 3 -> 6*(3-1)
20 / 7 = 2 -> 7*(2-1)
...
10까지 -> 절반까지

-1을 하는 이유는, 위 문제에서 자기 자신은 약수로 사용하지 않기 때문에 -1을 합니다.

 

즉, n을 입력받았을 때, 2부터 n/2까지 나눈 후 -1 한 값으로 해당 약수의 개수를 구하고, 개수와 약수를 곱한 값을 모두 더하면, 1부터 n까지의 실질적 약수 합을 구할 수 있습니다.

---

03. 정답 코드

// 골드 5 - 2247번 : 실질적 약수
// 작성자 : free4760(jeonghoe22)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 실질적 약수 : 1과 자기 자신(N)을 제외한 약수
// 6 -> 2,3
// 13 -> x

// SOD 함수 -> 실질적 약수의 합
// SOD(6) = 5
// SOD(13) = 0

// CSOD(n) = SOD(1) + ... SOD(n)

// 1    0
// 2    0
// 3    0
// 4    2
// 5    0
// 6    2,3
// 7    0
// 8    2,4
// 9    3
// 10   2,5
// 11   0
// 12   2,3,4,6
// 13   0
// 14   2,7
// 15   3,5
// 16   2,4,8
// 17   0
// 18   2,3,6,9
// 19   0
// 20   2,4,5,10

// 20 -> / 2 = 10 -> 2*(10-1)
// 20 -> / 3 = 6 -> 3*(6-1)
// 20 -> / 4 = 5 -> 4*(5-1)
// 20 -> / 5 = 4 -> 5*(4-1)
// 20 -> / 6 = 3 -> 6*(3-1)
// 20 -> / 7 = 2 -> 7*(2-1)
// 10까지 -> 절반까지

const int DIV = 1'000'000;

int csod(const int n)
{
    const int half = n / 2;
    int sum = 0;
    for(int i = 2; i <= half; i++)
    {
        int count = n / i;
        sum += (i * (count-1));
        sum %= DIV;
    }

    return sum;
}

int main()
{
    // 입출력 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    // 정수 n
    int n;
    cin >> n;

    cout << csod(n) << "\n";
}

 

 

---

 

읽어주셔서 감사합니다.

틀린 내용 지적은 언제나 환영입니다!