백준 1351 무한 수열 자바(java)

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

1351번: 무한 수열

 

풀이 방법

map 을 활용한 dp 의 메모이제이션 기법을 사용한다. 메모이제이션이란 동일한 계산이 반복 사용될 때 이전에 계산해놨던 값을 저장해놓고 사용하여 실행 시간을 줄이는 기법이다. 따라서 동작 방식은 A(i) 값이 이미 dp에 저장되어 있다면 dp 값을 반환하고, 없다면 A(i/p) + A(i/q) 를 재귀 호출을 통해 구하여 값을 구하여 반환한다.

dp 사용 시 배열로 선언하지 않는 이유는 메모리 제한이 128MB 인데 N 의 범위가 10^12 까지이므로 메모리 초과가 일어나기 때문이다. map 을 이용하여 사용되는 A값만 저장할 수 있도록 하면 메모리를 줄일 수 있다.

 

입력값의 범위에 주의하자!!!

입력값 범위가 10^12인 점은 간과하고 처음에 int 형으로 선언하여 런타임 오류가 났다.

int 는 32bit 이므로 2^31 = 약 10^9 까지 표현된다. 따라서 64bit인 long 형으로 선언해주어야 한다.

입력 조건을 제대로 확인하자.

 

코드

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

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

    public static void main(String[] args) {
        // N, P, Q 입력
        Scanner sc = new Scanner(System.in);
        N = sc.nextLong();
        P = sc.nextLong();
        Q = sc.nextLong();
        map.put(0L, 1L); // A[0]은 1의 값을 가짐

        System.out.println(A(N)); //A[N] 구하여 출력
    }

    // A 값 구하는 재귀 함수
    public static Long A(long i) {
        if (map.containsKey(i)) { // dp 에 이미 저장된 값이면 값 반환
            return map.get(i);
        }
        // dp 에 없다면 재귀호출하여 값을 구하고 dp 에 저장
        map.put(i, A(Math.floorDiv(i, P)) + A(Math.floorDiv(i, Q)));
        return map.get(i);
    }
}