[백준 1351번] 무한 수열 - JAVA

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

1351번: 무한 수열

풀이

사용한 알고리즘: DP

 

풀이전략

문제에서 주어진 식대로
d[i] = d[i/P] + d[i/Q] 를 사용하여 N에서의 An을 구한다.

단, Bottom-up 방식을 사용하면 i가 1~N까지 모든 경우의 수를 구하게 되는데
위 방식에서 Map에 많은 노드들이 삽입되어 메모리초과가 발생한다.

따라서 Top-down 방식을 사용하여 메모이제이션하는 수를 줄여야한다.
Top-down 방식을 사용하면 i가 1~N까지의 모든 경우의 수를 구하지 않고,
N에서 부터 정말 필요로하는 값들만을 저장해두므로 메모리초과가 발생하지 않는다.

또한 DP문제이기 때문에 함수를 통해 재귀하는 과정에서 
미리 구했던 수들은 다시 계산할 필요없도록 미리 구해둔 값이면 그 값을 그대로 사용한다.
만약 이를 구현하지 않으면 시간 초과가 발생한다.

마지막으로 문제에서 N의 범위가 0<=N<=10^12 인것을 확인할 수 있다.
이는 int형으로는 표현할 수 없는 수이다.
따라서 long 타입을 사용해야하는데, 배열의 인덱스에는 int 타입만을 사용할 수 있기에,
메모이제이션을 배열로 구현할 수가 없다.

따라서 Map을 사용하여 이를 해결한다.
Map은 어떤 타입이라도 사용할 수 있어 Long을 사용하면, N의 범위를 만족시키면서
DP를 활용해 문제를 해결할 수 있다.

 

제출코드

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

public class Main{
    static long N,P,Q;
    static Map<Long,Long> map = new HashMap<>();
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Long.parseLong(st.nextToken());
        P = Long.parseLong(st.nextToken());
        Q = Long.parseLong(st.nextToken());

        map.put(0L,1L);
        bw.write(func(N)+"\n");
        bw.flush();
        bw.close();
    }

    static long func(long num){
        if(map.containsKey(num)) return map.get(num);
        
        long first=func(num/P);
        long second=func(num/Q);
        map.put(num,first+second);

        return first+second;
    }
}