[99클럽 5기 코테 스터디 TIL 25일차] 무한 수열 (feat. 동적계획법)

1) 문제

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

 

2) 해결

이 문제는 메모이제이션을 활용한 동적 계획법(DP, Dynamic Programming) 을 사용하여 해결할 수 있습니다.
기본적인 아이디어는 재귀(Recursion) + 메모이제이션(Memoization) 을 사용하는 것입니다.

문제 풀이 접근

1. 기본 점화식 정의
   • A[i] = A[i/P] + A[i/Q] (단, A[0] = 1)
   • 이 점화식을 그대로 재귀적으로 구현하면 중복 계산이 발생하여 시간 초과가 발생할 가능성이 높습니다.
2. 메모이제이션을 활용한 최적화
   • 중복 계산을 방지하기 위해 해시맵(HashMap) 자료구조를 사용한 메모이제이션을 활용합니다.
   • 이미 계산된 값을 저장하여 불필요한 연산을 줄입니다.
3. 입력 범위 고려
   • N의 최대 값이 10¹²(1조) 로 매우 크므로, 일반적인 배열로 저장하면 메모리 초과가 발생합니다.
   • 따라서 해시맵(HashMap)을 활용한 DP 를 적용합니다.

import java.util.*;

public class InfiniteSequence {
    static long P, Q;
    static Map<Long, Long> memo = new HashMap<>();

    public static long getA(long i) {
        if (i == 0) return 1; // 기본 값
        if (memo.containsKey(i)) return memo.get(i); // 메모이제이션 확인
        
        // 점화식 적용: A[i] = A[i/P] + A[i/Q]
        long result = getA(i / P) + getA(i / Q);
        memo.put(i, result); // 계산 결과 저장
        
        return result;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long N = sc.nextLong();
        P = sc.nextLong();
        Q = sc.nextLong();
        
        System.out.println(getA(N));
        sc.close();
    }
}

코드 해석

1. 입력 받기
   • Scanner 를 이용하여 N, P, Q 값을 입력받습니다.
2. 메모이제이션을 위한 해시맵(HashMap) 사용
   • memo 라는 HashMap<Long, Long> 을 사용하여 A[i] 값을 저장합니다.
   • 일반 배열을 사용하면 N이 최대 10¹² 이므로 메모리 초과가 발생할 수 있지만, 해시맵은 필요한 값만 저장하므로 효율적입니다.
3. 재귀 함수 (getA)
   • 기저 사례(Base Case): A[0] = 1 이므로 i == 0 일 때 1을 반환합니다.
   • memo.containsKey(i) 를 사용하여 이미 계산된 값이 있다면 그대로 반환하여 중복 연산을 방지합니다.
   • 점화식을 이용하여 A[i] = A[i/P] + A[i/Q] 를 계산한 후, 해시맵에 저장하여 메모이제이션 합니다.
4. 출력
   • getA(N) 을 호출하여 결과를 출력합니다.