[백준] 17427 약수의 합2 (Java)

✉️문제

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

17427번: 약수의 합 2

 

📝 접근

https://brightmango.tistory.com/345

[알고리즘] 약수 알고리즘

위의 포스터에 나온 1번 2번 방식은 시간 초과로 사용할 수 없다. 따라서 배수를 이용한 약수의 합 구하는 방법을 이용한다.

 

🗝 문제풀이

먼저 문제를 이해해 보자. g(N)을 구하는 문제이고 g(N)은 N이하 자연수 각각의 약수의 합을 더한 값이다. (아래 그림을 보면 이해가 쉽다)

g(N) 구하는 방법 예시

 

다음 그림을 통해 이전 포스팅에서 설명한 배수를 이용한 약수 개수 구하기를 이해해보자.

• 6이하의 자연수 중에서 1을 약수로 갖는 수의 개수 = 6
• 6이하의 자연수 중에서 2를 약수로 갖는 수의 개수 = 3
• 6이하의 자연수 중에서 3을 약수로 갖는 수의 개수 = 2
• 6이하의 자연수 중에서 4를 약수로 갖는 수의 개수 = 1
• 6이하의 자연수 중에서 5를 약수로 갖는 수의 개수 = 1
• 6이하의 자연수 중에서 6를 약수로 갖는 수의 개수 = 1

 

이번 문제에서는 개수가 아닌 2의 배수를 모두 더해야 하므로 N / M * M을 해줘야 한다.

 

[코드]

import java.util.Scanner;

public class B17427R {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        long answer = 0;
        for(int i = 1; i <= n; i++) {
            answer += n / i * i;
        }

        System.out.println(answer);
    }
}