[수학] BOJ17427 약수의 합 2 - 오답노트

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

17427번: 약수의 합 2

 

- 문제 파악

자연수 N이 주어지면 1부터 N까지 각 자연수 마다 약수의 합을 모두 더하는 문제

 

- 나의 시도

무식하게 1부터 약수 구하여 더하고 를 N까지 반복, 하지만 자료형은 신경써서 unsigned long long 으로 답을 도출 하였으나.. 결과는 시간 초과 log(N) 이 되도록 로직을 구성하려고 시도했다.

자연수 k의 배수는 자연수 k의 약수 + 자기 자신

이라는 아이디어로 접근하였으나, 공배수를 처리해야하는 모순에 도달했다.

 

- 정답

1부터 N까지 약수를 나열 해놓고 1부터 N까지 그 개수를 세어보면 아래와 같다.
1 : N/1 개
2 : N/2 개
3 : N/3 개
4 : N/4 개
.
.
.
N : N/N 개

위에서 극단적으로 봤을때 1은 모든 수의 약수가 됨으로 (자기 자신도) 1은 반드시 N개가 존재한다. 또 N은 1부터 N까지의 약수 중에 오로지 자기 자신만 존재하므로 1개가 존재한다. 그러므로 코드는 아래와 같다.

 

#include "bits/stdc++.h"

using namespace std;

int main()
{
    int n;
    cin>>n;
    
    unsigned long long ans = 0;
    
    for(int i = 1 ; i <= n ; i++ )
    {
        unsigned long long tmp = n/i; // i의 개수
        ans += (i * tmp);
    }
    
    cout<<ans;
}

 

- 느낀점

 관찰력이 매우 부족했다. 단 몇줄이면 끝날것을 몇십줄로 만들다니.. 조금 더 면밀하게 패턴을 파악해보자