[BOJ/JAVA] 1351번: 무한 수열

1351번: 무한 수열

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

키워드

무한 수열 A는 다음과 같다.

• A_0 = 1

• A_i = A_⌊i/P⌋ + A_⌊i/Q⌋ (i ≥ 1)

N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오.

• 0 ≤ N ≤ 10^12

• 2 ≤ P, Q ≤ 10^9

---

구현

• 중요한 것은 N, P, Q의 범위가 매우 크다는 것이다.

• 배열로 만들기에는 너무 크기 때문에, Map을 이용하여 필요한 데이터만 저장하도록 하자.

• int 대신 long 자료형을 이용하자

statch HashMap<Long, Long> cache

A_i에서 i일 때 A_i의 값을 저장한다.

statc long dp(long index)

1. index가 0인 경우
   • 1을 반환한다.

2. 캐시값이 존재하는 경우
   • 캐시값을 반환한다.

3. A[index] = A_[index/P] + A_[index/Q] 를 계산한다.

---

코드

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

public class java_1351 {
    static long N;
    static int P, Q;

    static HashMap<Long, Long> cache;

    public static void main(String[] args) throws IOException {
        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());

        long result = solution();

        System.out.println(result);

        br.close();
    }

    private static long solution() {
        cache = new HashMap<>();

        if (N == 0) {
            return 1;
        }

        long result = dp(N / P) + dp(N / Q);

        return result;
    }

    private static long dp(long index) {
        // 기저사례: i가 0인 경우
        if (index == 0) {
            return 1;
        }

        // 기저사례: 캐시값이 존재하는 경우
        if (cache.getOrDefault(index, (long) -1) != -1) {
            return cache.get(index);
        }

        // 값 계산하기
        cache.put(index, dp(index / P) + dp(index / Q));

        return cache.get(index);
    }
}

---

Uploaded by N2T