[백준] 17425번 - "약수의 합" (Java)

www.acmicpc.net/problem/17425

17425번: 약수의 합

---

- 난이도 : 골5

약수 개념이 가미된 전형적인 테스트 케이스 문제입니다. 몇 가지 사항만 주의해준다면 충분히 풀 수 있습니다.

 

시간 복잡도는 해당 자연수의 약수의 합을 저장(fx)하는 코드 NlgN,

이전 약수의 합들을 저장(dp)하는 코드 N,

테스트 케이스(while) 갯수만큼 코드를 진행하는 T,

 

즉, NlgN + N + T에서 N은 NlgN보다 작으니 최종 시간복잡도는 NlgN + T입니다.

주어진 시간 제한은 1초이고 약 1억개의 데이터 안에서 문제를 푼다고 가정하면

빅오 표기법 1,000,000 * lg1,000,000 + 100,000 은 1억보다 작으니 충분히 시간 제한안에 풀 수있는 코드입니다. 

 

브루트 포스를 가장한 테스트 케이스 문제는 테스트 케이스가 주어질 때마다 문제를 해결하고자 하면 시간 초과가 나기 쉽습니다. 그래서 미리 문제를 해결해놓고 테스트 케이스에 따라서 답만 도출하는 것이 바람직합니다. 

 

이 문제는 전형적인 약수의 개념으로 문제를 해결하고자 하면 시간 초과가 납니다. 그래서 약수의 반대인 배수의 아이디어로 정답을 도출하는 것이 중요합니다. 

 

예를 들어, 아래 코드는 약수의 개념으로 문제를 풀 경우입니다. 이 아이디어는 매 수마다 모든 약수를 도출하기 때문에 시간 초과가 납니다. 

for(int i=2; i<=n; i++) {
	for(int j=1; j<=i; j++ {   	
        if(i % j == 0) {
    		fx[i] += j;
        }
    }
}

 

추가적인 설명은 주석으로 하겠습니다.

 

  코드

public class BOJ_17425 {
	// BOJ / 17425번 / 약수의 합 / 수학 / 골5
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();
		
		int t = Integer.parseInt(br.readLine());
		
		long fx[] = new long[1000001]; // 해당 자연수의 모든 약수를 더한 변수.
		long dp[] = new long[1000001]; // 해당 자연수 이하의 모든 fx값을 더한 변수.
		
		// 1은 모든 수의 약수니까 전부 넣어준다.
		Arrays.fill(fx, 1);
        
		/*
		 배수 아이디어. (i*1, i*2, i*3....)
		 i는 2부터 n까지 i를 약수를 갖는 모든 수다.
		 시간복잡도는 NlgN이다.
		 j는 i*j까지만 반복한다. 예를 들어 i가 2일 경우 j는 오십만까지만 가면된다.
		 2 * 오십만은 백만이니까.
        	*/
		for(int i=2; i<fx.length; i++) {
			for(int j=1; i*j<fx.length; j++) {
				fx[i*j] += i;
			}
		}
		
		// g(x), x보다 작거나 같은 모든 자연수y의 f(y)값을 더한 변수.
		for(int i=1; i<dp.length; i++) {
			dp[i] += dp[i-1] + fx[i];
		}
		
		// 테스트 케이스에 따라서 답만 도출한다.
		while(t-- > 0) {
			int input = Integer.parseInt(br.readLine());
			
			sb.append(dp[input]).append("\n");
		}
		
		System.out.println(sb);
	}
}

 

 

피드백은 얼마든지 환영합니다.