[BOJ 17427] 약수의 합 2

약수의 합 2 (17427번)

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

시행착오

• 첫번째 시도 : 처음 문제를 봤을 때 시간 제한이 0.5초인걸 보고 하나씩 약수를 구한 후 더하면 시간초과가 발생할 것 같았다.
  • 대략 1억번 반복할 때 1초라고 얘기를 들은적이 있는데 1,000,000 * 1,000,000이면 1조라는 큰 값이 나온다.
  • 시간복잡도 : O(N^2)
• 두번째 시도 : 소인수분해를 통해서도 약수의 합을 구할 수 있어서 구현했지만 10,000을 넣어도 시간이 오래걸렸다.
  • 아마 소인수분해를 할 때 계속해서 나누기 때문에 오래걸린 것으로 판단했다.
  • 시간복잡도 : O(N^2)
• 마지막 시도 : 우선 1~10까지의 약수를 모두 구해보고 어떤 규칙이 있지 않을까 생각했다. 왜냐하면 분명 시간내에 풀기 위해서는 O(N)의 시간복잡도는 가져야한다고 판단했기 때문이다.
  • 그래서 규칙을 찾아본 결과 N을 1~N까지 나눈 값이 1~N 까지의 약수들을 모두 포함하고 있었다.
    1 2 3 4 5 6 7 8 9 10 11 12

    1~10까지의 약수들 중 1의 개수 : 10개 2의 개수 : 5개 3의 개수 : 3개 4의 개수 : 2개 5의 개수 : 2개 6의 개수 : 1개 7의 개수 : 1개 8의 개수 : 1개 9의 개수 : 1개 10의 개수 : 1개 를 가지게 됨을 알 수 있었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long answer = 0;

        for(int i=1; i<=N; i++) {
            answer += i * (N/i);
        }

        System.out.println(answer);
    }
}