[백준 1351] 무한 수열(Java)

문제 링크 : https://www.acmicpc.net/problem/1351

이 문제는 재귀함수와 map을 이용하여 풀 수 있습니다.

무한수열 특성상 i를 파라미터로 가지는 재귀함수를 반복해서 return A(i/p) + A(i/q)를 이용하면 쉽게 결과를 구할 수 있습니다. 하지만 값이 충분히 크기 때문에 단순히 재귀로 반복하게 되면 시간 초과가 발생합니다.

이를 위해 map에 이미 연산을 실행한 결과를 저장하여 리턴합니다. i/p의 값을 키로, A(i/p)의 값을 벨류로 하여 저장한 후 재귀함수 연산을 수행하기 전 map을 우선탐색하여 값이 존재한다면 그 값으로 연산을 수행합니다.

다음은 코드입니다.

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

class Main{
    static long N,P,Q;
    static Map<Long, Long> check = new HashMap<>();

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Long.parseLong(st.nextToken());
        P = Long.parseLong(st.nextToken());
        Q = Long.parseLong(st.nextToken());

        System.out.println(solve(N));
    }

    static long solve(long idx){
        if(idx == 0) return 1;
        else return getSum(idx/P) + getSum(idx/Q);
    }

    static long getSum(long idx){
        long res = 0;
        if(check.containsKey(idx)) res = check.get(idx);
        else{
            res = solve(idx);
            check.put(idx, res);
        }
        return res;
    }
}