[Algo] 백준 17427 약수의 합 2

문제 바로가기 : https://www.acmicpc.net/problem/17427

메모리 : 14324KB

시간 : 140 ms

언어 : Java 11

---

코드

import java.io.*;
import java.util.*;

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 = 0L;
        for (int i = 1; i <= N; i++) {
            for (int j = i; j <= N; j += i) {
                answer += i;
            }
        }

        System.out.println(answer);
    }
}

 

풀이

N보다 작은 자연수들의 약수들의 합을 구하는 문제이다. 누적합을 차용하면 쉽게 풀린다. 시간제한이 0.5초이기때문에 함부로 for문을 쓰다가는 시간초과를 면치 못할 것이다. 소수를 구할 때 사용하는 에라토스테네스의 체를 조금 변형하면 쉽게 약수를 구할 수 있다. 소수란 1과 자기자신만을 약수로 가지는 수이므로 결국 약수를 가졌는지 아닌지 판단하는 풀이이기 때문이다. 1부터 N까지 배수를 구해가며 i를 약수로 가진 경우를 더해주는 것이다.