백준#17425 약수의 합 구하기

문제

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.

자연수 N이 주어졌을 때, g(N)을 구해보자.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주어진다. 둘째 줄부터 테스트 케이스가 한 줄에 하나씩 주어지며 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

각각의 테스트 케이스마다, 한 줄에 하나씩 g(N)를 출력한다.

예제 입력 1 복사

5
1
2
10
70
10000

예제 출력 1 복사

1
4
87
4065
82256014

---

<풀이>

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

public class NUM17425 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		//많은 양의 데이터를 입력받는경우 BufferedReader가 더 효율적이며 작업속도가 빠름
		
		long[] sum=new long[1000001];
		Arrays.fill(sum,1);		// 배열의 값을 1로 초기화, 모든 수는 1을 약수로 가지기 때문
		
		for(int i=2 ; i<=1000000 ; i++) {	//i의 배수가 되는 인덱스에 i를 대입
			for(int j=1 ; j*i<=1000000; j++) {		  
				sum[j*i]+=i;
			}
			sum[i]+=sum[i-1];	// 변수i 이하의 모든수의 약수의 합을 구해야하므로 이전과 합함
		}
		int N = Integer.parseInt(br.readLine()); //입력받을 수의 개수
		for(int k=0; k<N; k++) {
			int num = Integer.parseInt(br.readLine()); //약수의 합을 확인할 수
			bw.write(sum[num]+"\n");
		}
		bw.flush(); //남아있는 데이터를 모두 출력시킴
		bw.close(); //스트림을 닫음
	}
}

/*
 *F(n)의 값들을 저장할 배열생성(최대1,000,000이지만 1번인덱스를 시작으로 잡아서 1,000,001로 범위설정)
 *모든 수는 1을 약수로 가지므로 배열의 모든 인덱스에 1저장
 *for문을 돌리면서 해당 값의 배수인 배열에 값을 집어넣음 (ex. i*j=3 일때, index3,6,9...에 저장)
 *F(n) 값들의 합을 차례로 더함
 */

처음엔 문제를 그대로 직역하고 풀이를 했다. 이중포문을 잔뜩 쓰면서 했더니 시간초과 탈락..ㅜㅜ

그럼 약수를 어떻게 구하란건지 재귀를 해야하는건지 고민하면서 구글링을 해보니 생각도 못해본 방법이 나왔다.

2가 10의 약수라는것은 곧 10이 2의 배수이기도 한다는 점을 이용해야했던것이다. 

이렇게 기본적인거도 생각을 못해내는데 코테..가능할까? 싶었지만 뭐 하다보면 되겠지 하는맘으로 패쓰

포문을 돌려가며 입력값 하나하나의 약수를 찾는거보다 변수를 키워가며 배수가 되는 인덱스에 값을 집어넣는게 훨씬 작업속도가 빨랐다. 

솔직히 위 코드 중 핵심적인 부분은 완전히 내가 작성했다 할 수 없다. 구글에 있는 이 코드 저 코드 읽어가며 이해하기 바빴던지라..ㅜㅜ 그래도 코드를 읽으며 이해하는 과정 하나하나가 나한테 도움이 될거라고 믿는다. 뭐 완벽하지않은 공부도 있는법이니까ㅎㅎ;; 조금씩 보완해나가면서 더 열심히 해보자