백준 1351번 - 무한 수열

문제

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

리뷰

DP를 구현함에 있어 HashMap을 활용하는 문제였다.
통상적인 DP 문제는 배열을 활용하여 구현하나, 이 문제의 경우 주어진 $N$의
최대값이 $10^{12}$(1조)이기 때문에 배열로 구현할 경우 메모리 제한을 통과하기
어려운 구조였다. 이 지점에서 $A_N$ 을 구하는데 필요한 $A_{N/P}, A_{N/Q}$만
HashMap 을 활용하여 구현하면 해당 조건을 통과할 수 있을 것이라 판단했다.

점화식을 그대로 로직으로 구현하고, map 에 값이 존재하지 않는 경우만 재귀적으로
값을 도출하여 map에 저장한 후 반환하는 식으로 DP를 구현하였다.
$N,P,Q$의 값이 Integer 를 넘어설 수 있기에 Long 으로 타입을 정의하였다.

getValue 내에서 map에 값이 없는 경우 2번의 재귀 호출이 발생하므로
전체 로직의 시간복잡도는 $O(\log N)$으로 수렴한다. 따라서 $N$이 1조인 경우에도
$\log (1T)=40$ 이므로 무난하게 주어진 시간 제한을 통과한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

import static java.lang.Long.*;

public class Main {
    static Map<Long, Long> map = new HashMap<>();

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

        map.put(0L, 1L);
        System.out.println(getValue(N, P, Q));
        br.close();
    }

    static Long getValue(Long N, Long P, Long Q){
        if(N==0) return 1L;
        else{
            Long value1=N/P;
            Long value2=N/Q;

            if(map.get(N)==null)
                map.put(N, getValue(value1, P, Q)
                        +getValue(value2, P, Q));

            return map.get(N);
        }
    }
}

결과