[BOJ - JAVA] 17427 - 약수의 합2

# 주소

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

17427번: 약수의 합 2

 

# 문제

# 문제 해설 및 코드 리뷰

 

package first;

import java.util.*;
public class sex{
    int sum = 0;
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int sum = 0;
        for(int i = 1; i <= n; i++) {
        	sum += coll(i);
        }
        System.out.print(sum);    
    }
    public static int coll(int n) {
    	int co = 0;
        for(int i = 1; i <= n; i++){
            if(n % i == 0) {
            	co += i;
            }
        }
        return co;
    }
}

처음에 제출한 코드입니다. 이클립스로 예제들을 확인해보면 전부 정답으로 뜨는데 백준사이트에 제출하니

자꾸 시간초과라고 떴던 코드입니다. 

아마 저 코드 내역을 그대로 Buffered 로 입력문을 작성했어도 시간 초과가 뜰 것 같습니다.

다른 함수를 선언하여 거기서 또 for문을 돌렸기 때문에 100만 단위의 정수까지 계산하기에는 시간 낭비가 심합니다.

import java.io.*;

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

 

그래서 한 개의 for문으로 정답을 추려내보았습니다.

표를 통해 살펴보겠습니다.

1	1
2	1	2	-	-	-	-	-	-	-
3	1	-	3	-	-	-	-	-	-
4	1	2	-	4	-	-	-	-	-
5	1	-	-	-	5	-	-	-	-
6	1	2	3	-	-	6	-	-	-
7	1	-	-	-	-	-	7	-	-
8	1	2	-	4	-	-	-	8	-
9	1	-	3	-	-	-	-	-	9

보시면 1은 늘 한 개씩 들어있으므로 총 9개가 필요합니다.

2는 4개, 3은 3개, 4는 2개, 5는 1개... 9는 1개 필요합니다.

이는 n이 9가 입력되었을 때 (n / i) * i 를 ans에 계속 더하여 작성할 수 있습니다.

이전에 코딩한 것과 비교해보면 확실히 for문이 한 개 뿐이니, 메모리 낭비도 덜하고 시간도 절약할 수 있습니다.

실행해보면 시간초과가 뜨지 않고 정답이 되는 것을 확인할 수 있으실 겁니다!

감사합니다.