[백준] Java 17427 약수의 합 2

문제

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

알고리즘

수학

풀이

N까지의 모든 약수의 합을 구해야 한다.
일단 시간제한을 잘 봐야 한다. 시간제한이 0.5초이다. 대략적으로 1억이 1초이고 N은 백만까지 가능하다.
여기서 우리는 N제곱으로 풀면 시간초과가 나온다는 것을 알아야 한다. 나도 아직 한번에 알지는 못하지만 계속 풀어보면서 확인해야 한다.

기존에 생각할 수 있는 풀이

1. 먼저 각 숫자의 약수를 구하는 방법은 그 숫자까지 for문을 돌려서 나누어 떨어지면 약수라고 본다.
2. 아니면 루트 N까지만 구하고 그 수와 그 수를 나눈 몫을 약수라고 보면 된다.
3. 일단 각 숫자의 약수를 구한 다음에 이 약수들을 모두 더해주어야 한다.
4. 때문에 모든 약수의 합을 구하는데 걸리는 시간은 N log(N)이나 N log(루트N)이다.
5. 이 방법대로면 제일 큰 숫자 백만의 제곱까지 구하는 시간이 최악으로 걸리는 시간이다.
6. 백만의 제곱은 1조이므로 1억이 1초면 10,000초가 걸리기 때문에 시간초과가 나오게 된다.

밑에 풀이는 사실 외워야 한다. 기존에 생각해낼 수 없는 풀이이기 때문에 외우고 잊어버리지 않게 꼭 기억해야 한다.

새로운 풀이

1. 1부터 N까지 for문을 돌면서 1이 몇번 나오는지 계산해준다. 그 계산은 (N / i) * i 이다.
2. N이 7이고 i가 1이라면 위 계산식은 7이 나오는데 1부터 7까지 1은 모든 수의 약수이다. 그러므로 모든 1의 합은 7이기 때문에 위 계산식이 맞다.
3. N이 7이고 i가 2라면 위 계산식은 6이 나오는데 1부터 7까지 2는 총 3번 나온다. (2, 3, 6의 배수) 그러므로 모든 2의 합은 6이므로 위 계산식이 맞다.
4. 이런식으로 N까지 for문을 돌려서 모든 합을 다 더해주면 정답이 나온다.

코드

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

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;

        // 1부터 N까지 for문을 돌린다.
        for (int i = 1; i <= n; i++) {

            // (n / i) * i의 계산식으로 각 숫자의 총 합을 구해주고 그 합을 answer에 넣어준다.
            answer += (long) (n / i) * i;
        }

        // 마지막으로 그 답을 출력해준다.
        System.out.println(answer);

    }
}