[SW Expert] 5213. 진수의 홀수 약수

생각

Github - https://github.com/hellojdh/Code/blob/master/src/swexpert/d4/Q5213.java

L과 R의 수가 주어진다. L과 R사이의 수에서 그 수들의 약수의 홀수 값만을 모두 더한 값을 출력하여라.
예를 들어 L=6 R=10일 경우 케이스는 다음과 같다.
6 일경우 약수 1,3이 홀수이므로 4
7 일경우 약수 1,7이 홀수이므로 8
8 일경우 약수 1 이 홀수이므로 1
9 일경우 약수 1,3,9가 홀수이므로 13
10 일경우 약수 1,5가 홀수이므로 6
따라서, 4+8+1+13+6 = 32가 답이된다.

처음 생각

L과 R의 범위가 1_000_000 백만 이므로 일반적으로 풀면 시간 초과가 나올것이라 생각하였다.

다음 생각

에라토스테네스 체와 같이 미리 모든 값 마다 모든 약수의 합을 구해놓는 배열을 만들기로 하였다.

▶ 홀수만 확인하면 되기 때문에 첫 반복문의 증가값을 i+=2로 값을 주었고, 이 i 값을 다음 반복문의 변수인 j 값을 1부터 곱하면 그 수의 약수가 된다. 코드를 보면 이해하기가 좀 더 쉽다.

▶ 미리 구한 후, arr[L]부터 arr[R] 까지 더하였더니 시간 초과가 나왔다.

다다음 생각

앞서 약수의 합을 미리 구한것을 가지고 그 약수까지 이전 약수값을 모두 더한 값을 만들어 주었다.

▶ 따라서 arr[L]에는 1~L 까지의 모든 홀수 약수의 합이 들어있고 arr[R]에는 1~R까지의 모든 홀수 약수의 합이 들어가있다.
▶ 즉, arr[R]-arr[L-1]을 하면 L~R사이의 모든 수의 홀수 약수들의 합이 계산된다.

방안

1) 에라토스테네스 체와 같이 미리 구하는 방법은 많은 연산량을 요구할 때, 효율적인 방법인것 같다. 실제로 주어진 시간 제한은 Java의 경우 7초이지만 600ms에 통과하였다.

package swexpert.d4;
 
import java.io.IOException;
import java.util.Scanner;
 
public class Q5213 {
     public static void main(String[] args) throws IOException {
           Scanner sc = new Scanner(System.in);
           StringBuilder sb = new StringBuilder();
           int tc = sc.nextInt();
            // 미리 구해 놓기
           solve();
           for(int i=1;i<=tc;i++) {
               int L = sc.nextInt();
               int R = sc.nextInt();
               long sum = 0;
               // R~L까지 수들의 합
               // arr[R]에는 1~R 까지의 모든 합이 들어있다.
               sum = arr[R]-arr[L-1];
               sb.append("#"+i+" "+sum+"\n");
           }
           System.out.print(sb);
       }
       
       static long[] arr = new long[1000001];
       private static void solve() {
           // 약수 미리 더하기
           for(int i=1;i<=1000000;i+=2) {
               for(int j=1;(i*j)<=1000000;j++) {
                   arr[(i*j)] += i;
               }
           }
           // 더한 값의 이전값 미리 더하기
           for(int i=1;i<=1000000;i++) {
               arr[i] += arr[i-1];
           }
       }
}