백준 17427

약수의 합

입력받은 수의 약수의 약수의합을 구하는 문제이다
약수의 약수의 합이라는 말처럼 이중반복문을 쓰면 될꺼같은 느낌이 들었다.
하지만 scanner와 반복문2번과 if문 두번을 쓰니 타임아웃이 떠버렸다

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        long result = 0; // g(N) 값을 저장할 변수

        for (int i = 1; i <= N; i++) {
            result += f(i);
        }

        System.out.println(result); // 최종 g(N) 값을 출력
    }

    // f(A)를 계산하는 함수
    public static long f(int A) {
        long sum = 0;
        int sqrtA = (int) Math.sqrt(A);
        for (int i = 1; i <= sqrtA; i++) {
            if (A % i == 0) {
                sum += i; // i를 sum에 더함
                if (i != A / i) { // i와 A/i 가 다를 경우에만 추가
                    sum += A / i;
                }
            }
        }
        return sum;
    }
}

해결방법으로는
다른 알고리즘:Dynamic Programming

DP(Dynamic Programming)는 복잡한 문제를 간단한 여러 하위 문제로 나누어 해결하는 방법론이다. 각 하위 문제의 해결을 저장하고, 그 해결을 이용해서 원래 문제를 해결하는 것이 핵심이다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();

        long[] dp = new long[N + 1];  // dp[i]는 i의 약수의 합을 저장합니다.

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j * i <= N; j++) {
                dp[i * j] += i;
            }
        }

        long result = 0;
        for (int i = 1; i <= N; i++) {
            result += dp[i];
        }

        System.out.println(result);
    }
}

느낀점은 타임아웃을 처음 경험해봤다.
간단한 문제만 풀어서 알고리즘을 적용을 안하고 문제를 보고 for문 이나 if문 여러번 쓰면 되겠지라고 생각했었다
하지만 최적화를 하면서 한줄의 코드를 재활용해서 시간을 줄이는게 더 효과적인 방법이구나를 꺠달았다