[BOJ][DP] 1351. 무한 수열 (java)

✏️ 문제 https://www.acmicpc.net/problem/1351

문제
무한 수열 A는 다음과 같다.A0 = 1Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1)N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오.

입력
첫째 줄에 3개의 정수 N, P, Q가 주어진다.

출력
첫째 줄에 AN을 출력한다.

 

🔢 알고리즘

 

#DP

 

 

🤯 풀이 방법

 

처음 제출한 코드는 ⬇️

수열이라고 1부터 하나씩 계산하며 올라가면 메모리 초과가 난다.

 

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

public class Main {
    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());

        HashMap<Long, Integer> map = new HashMap<Long, Integer>();
        map.put(0L, 1);
        for (long n = 1; n <= N; n++) {
            long A1 = n / P;
            long A2 = n / Q;

            map.put((long)n, map.get(A1) + map.get(A2));
        }

        System.out.println(map.get(N));

    }
}

 

 

그러므로 재귀를 이용해서 N부터 N/P, N/Q에 필요한 값만 찾으며 내려간다.

이때 71%에서 틀리면 어딘가에 long이 아닌 int를 사용해서 값 초과가 난거니 조심하자..

 

👾 구현 코드 (자바)

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

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

    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());
        P = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());

        map.put(0L, 1L);
        System.out.println(seq(N));

    }

    public static long seq(long N)  {
        if (map.containsKey(N)) {
            return map.get(N);
        }

        long result = seq(N / P) + seq(N / Q);
        map.put(N, result);
        return result;
    }
}