백준 17427번 : 약수의 합2

백준 17427번 : 약수의 합2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        sumOfDivisor(num);
    }
    public void sumOfDivisor(int n){
        long result = 0;
        for(int i = 1; i<=n; i++){
            result += (n/i)*i;
        }
        System.out.println(result);
    }
    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}

처음엔 2중 for문을 생각 했었는데. 입력 자연수가 1<= N <=1000000 이고, 주어진 시간은 0.5초라는 점에서 for문을 하나로 생각을 바꿔 풀이를 진행했다. 1시간 동안 생각을 하다가... 결국 폭풍검색... 복습 차원에서 이해한 내용을 바탕으로 직접 풀이를 해설 해보겠다.

약수를 구하는 것에서 규칙이 하나 있다. 만약 N이  6이라면

 

f(1)

f(1,2)

f(1,3)

f(1,2,4)

f(1,5)

f(1,2,3,6)

 

1은 6개 2는 3개, 3은 2개 4는 1개 ... 라는 규칙이 존재했다.

규칙대로 for문을 돌렸고,

 

6/1*1 = 6 = 1이 6개

6/2*2 = 6 = 2가 3개

...

6/6*6 = 6 = 6이 1개

 

n/i*i 라는 수식을 통해 해결했다.