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

문제 파악

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

풀이

점화식 : DP[N] = DP[N/P] + DP[N/Q] 

배열🚫, 반복문🚫

메모리 이슈로 배열을 N 크기(최대 10^12)만큼 선언해 두고 사용할 수 없다 😅
또한 피보나치를 풀이할 때처럼 DP[N] 계산 시 모든  [1, N]에 대해 값을 채워야 하므로, 연산량이 매우 커진다
불필요한 값(사용되지 않는 DP 배열의 부분)까지 계산해야 하므로 비효율적이다.

Map⭕️, 재귀 ⭕️

따라서 Map을 사용하는 방향을 선택했다.
해당 시간 복잡도는 O(1)이기 때문에 배열 접근과 차이가 나지 않을 것이다.

이를 탑다운식의 재귀로 풀이해보도록 하자

N = 100, P = 50,  Q = 30 를 예로 들어보자.

100번째 수 ➡️ [2번째 수 + 3번째 수] ➡️ [(0번째 수 + 0번째 수)+(0번째 수 + 0번째 수)]

0, 2, 3, 100번째 수의 공간만 필요로 하게 되며, 연산의 수도 눈에 띄게 준다.

재귀를 간단히 줄글로 정리해보자면 다음과 같다.

1️⃣ map의 N번째 수가 Key로 있을 경우 값을 반환해준다.
2️⃣ 없을 경우 N/P, N/Q번째 합을 더해서 반환해주도록 한다.
이때 N/P, N/Q번째 값에 대해서도 Map 내에 있는지 확인해주고, 없다면 다시 함수를 호출해 값을 불러올 수 있도록 하자.

tip) N의 범위가 너무 크기 때문에 엣지케이스를 미리 지정해 두고 입력해 보며 풀이하도록 하자.

1000000000000 2 3

코드

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

public class Main {
    private static Map<Long, Long> map;
    public static void main(String[] args) throws IOException {
        map = new HashMap<>();
        map.put(0L, 1L);
        String[] input = new BufferedReader(new InputStreamReader(System.in)).readLine().split(" ");
        long n = Long.parseLong(input[0]);
        int p = Integer.parseInt(input[1]);
        int q = Integer.parseInt(input[2]);
        long answer = getValue(n, p, q);
        System.out.println(answer);
    }
    public static long getValue(long n, int p, int q) {
        if(map.containsKey(n)) {
            return map.get(n);
        }
        long firstKey = n / p;
        long secondKey = n / q;
        map.putIfAbsent(firstKey, getValue(firstKey, p, q));
        map.putIfAbsent(secondKey, getValue(secondKey, p, q));
        return map.get(firstKey) + map.get(secondKey);
    }
}