"꾸준하고 완벽한 한 걸음"

PS/Baekjoon Online Judge

[백준 01354] 무한 수열 2 [Java]

kimyoungrok 2025. 3. 14. 00:55
728x90

문제

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

 


풀이

주어지는 N에 대해 $A_N$을 구하는 문제다.

단 N은 최대 $10^{13}$이며, 중복되는 계산을 최소화 해야한다.

범위가 넓기 때문에 Map을 사용해서 중간 계산을 기록하면 된다.

    private static long getA(long i) {
        if (i <= 0) {
            return 1;
        }
        if (A.containsKey(i)) {
            return A.get(i);
        }
        A.put(i, getA(i / P - X) + getA(i / Q - Y));
        return A.get(i);
    }

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/01354.java

728x90