[백준 1351] 무한 수열

▪︎ 문제

---

백준 1351 문제

▪︎ 알고리즘 설계

---

• 점화식을 그대로 재귀로 구현
  • A(n) = A(n / P) + A(n / Q)
  • 조건을 보면, 배열로는 구할 수 없음
    • 배열의 인덱스는 long 타입이 안됨. 무조건 int만 가능.
• 배열 대신 HashMap을 사용하는 이유
  • N이 최대 10^12이므로 배열 arr[N]을 만들 수 없다.
  • HashMap은 필요한 값만 저장하므로 메모리 효율적.
• N=7, P=2, Q=3
  • A(7) = A(7/2) + A(7/3) = A(3) + A(2)
  • A(3) = A(3/2) + A(3/3) = A(1) + A(1)
  • A(2) = A(2/2) + A(2/3) = A(1) + A(0)
  • A(1) = A(1/2) + A(1/3) = A(0) + A(0)
  • A(0) = 1
• 메모이제이션을 적용하면 A(1), A(2), A(3) 같은 값은 한 번만 계산된다.
  • 중복 계산 방지 → 메모이제이션
  • n이 큰 값일 때, 같은 n에 대한 계산이 여러 번 호출될 수 있다.
  • 이를 방지하기 위해 HashMap<Long, Long>을 사용하여 이미 계산한 값을 저장하고 재사용한다.

▪︎ 코드

---

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

class Main {

    static long P, Q;
    static Map<Long, Long> memo = 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());
        P = Long.parseLong(st.nextToken());
        Q = Long.parseLong(st.nextToken());

        System.out.println(calc(N)); // 무한 수열 계산
        
    }

    static long calc(long n) {
        if (n == 0) return 1;
        if (memo.containsKey(n)) return memo.get(n); // 중복 재귀 호출 피함

        long value = calc(n / P) + calc(n / Q);
        memo.put(n, value);
        return value;
    }
}

▪︎ 시간복잡도

---

O(M) (일반적인 입력에서 M은 log N 수준.)

▪︎ 틀린 이유

---

• 배열로 접근함
  • 배열의 인덱스는 long 타입 지원 안함 → 컴파일 에러
  • int로 바꿀 경우 N이 너무 커서 런타임 에러
• 해시 맵과 재귀 접근 생각 못함

▪︎ 느낀점 / 기억할 정보

---

• 큰 N(10^12)에서는 배열을 사용할 수 없으며, 필요한 값만 계산하고 저장하는 방식이 필요
  • 큰 입력은 DP 배열 불가 → 메모이제이션(HashMap) 필요
• HashMap은 동적 크기이면서 O(1) 조회가 가능하므로 메모이제이션에 최적
• 점화식을 그대로 재귀로 구현하고, 중복 계산을 막으면 큰 입력도 해결 가능하다.
• 문제에서 n/P, n/Q와 같이 계속 나눠지는 구조라면, 계산 깊이는 log N 수준으로 줄어든다.
  • 점화식에서 n이 나눠지는 형태 → 재귀 + 메모이제이션이 강력한 방법