[백준] 1354번 - 무한 수열 2 [Java]

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

 

[백준] 1354번 - 무한 수열 2 [Java]

[백준] 1354번 - 무한 수열 2 [Java]

---

1.  아이디어

 

이전 무한 수열 문제에서 수의 범위와 점화식의 모양만 약간 달라진 문제로 동일하게 Top-Down 다이나믹 프로그래밍으로 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 1351번 - 무한 수열 [Java])

---

2. 문제풀이

 

HashMap으로 메모이제이션해서 동일하게 구현했다.

---

3. 코드

 

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

public class Main {

    private static final Map<Long, Long> dp = 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 = Long.parseLong(st.nextToken());
        int P = Integer.parseInt(st.nextToken());
        int Q = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());
        int Y = Integer.parseInt(st.nextToken());

        System.out.println(recur(N, P, Q, X, Y));
    }

    private static long recur(long N, int P, int Q, int X, int Y) {
        if (N <= 0) return 1;
        if (dp.containsKey(N)) return dp.get(N);

        dp.put(N, recur(N / P - X, P, Q, X, Y) + recur(N / Q - Y, P, Q, X, Y));
        return dp.get(N);
    }

}

---

4. 후기