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

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

 

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

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

---

1.  아이디어

 

Top-Down 방식의 다이나믹 프로그래밍과 HashMap을 통한 메모이제이션으로 해결할 수 있다.

---

2. 문제풀이

 

수열의 특정 원소를 구하기 위해서 수열의 다른 두 원소의 합을 구해야 한다. 다른 두 원소도 역시 또 다른 두 원소의 합으로 이루어져 있고 해당 과정이 재귀적이므로 깊이 우선 탐색을 통해 구할 수 있다. 다만 이 과정에서 계산의 중복을 줄이기 위해 메모이제이션이 필요하고 수열의 길이가 int형 범위를 넘어갈 수 있어서 배열 대신 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());

        dp.put(0L, 1L);

        System.out.println(dfs(N, P, Q));
    }

    private static long dfs(long N, int P, int Q) {
        if (dp.containsKey(N)) return dp.get(N);
        dp.put(N, dfs(N / P, P, Q) + dfs(N / Q, P, Q));
        return dp.get(N);
    }

}

---

4. 후기