BOJ 1351 - 무한 수열

문제

무한 수열 A[0] = 1, A[i] = A[floor(i/P)] + A[floor(i/Q)]에서 A[N]을 구하라. N은 최대 10^12이다.

입력

한 줄에 N, P, Q가 주어진다.

출력

A[N]을 출력한다.

예제

입력	출력
`7 2 3`	`7`

풀이

HashMap 메모이제이션으로 필요한 값만 재귀적으로 계산한다.

N이 최대 10^12이므로 배열 대신 HashMap을 사용한다
solve(n): n이 0이면 1을 반환, 이미 계산되었으면 캐시 반환
solve(n/P) + solve(n/Q)를 계산하여 HashMap에 저장한다
N을 P, Q로 반복 나누면 log 스케일로 줄어들어 실제 계산 수가 적다

핵심 아이디어: N을 P, Q로 나누면 O(logP(N) * logQ(N))개의 고유 상태만 존재한다. 배열 대신 HashMap으로 희소 메모이제이션한다.

코드

package day399;
 
import java.io.*;
import java.util.*;
 
public class Day399BOJ1351무한수열 {
  static long N, P, Q;
  static Map<Long, Long> map = new HashMap<>();
 
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
 
    N = Long.parseLong(st.nextToken());
    P = Integer.parseInt(st.nextToken());
    Q = Integer.parseInt(st.nextToken());
 
    System.out.println(solve(N));
    br.close();
  }
 
  private static long solve(long n) {
    if (n == 0)
      return 1;
    if (map.containsKey(n))
      return map.get(n);
    long p = (long) Math.floor(n / P);
    long q = (long) Math.floor(n / Q);
    map.put(n, solve(p) + solve(q));
    return map.get(n);
  }
}

복잡도

시간: O(logP(N) * logQ(N)) - 고유 상태 수
공간: O(logP(N) * logQ(N)) - HashMap 저장

문제