[백준 | Java] 1351번 무한 수열 - Dynamic Programming, Map

1351번 / 무한 수열

❓ 무한 수열

🏷️ 관련 주제 : Dynamic Programming Map

---

💦 나의 시도

재귀함수를 이용한 $A_N$ 구하기

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

public class Main {
    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());
        long P = Long.parseLong(st.nextToken());
        long Q = Long.parseLong(st.nextToken());

        System.out.println(getAn(N, P, Q));
    }

    public static long getAn(long n, long p, long q) {
        if (n == 0) {
            return 1;
        }

        long sub1 = n / p;
        long sub2 = n / q;
        return getAn(sub1, p, q) + getAn(sub2, p, q);
    }
}

재귀함수 getAn()을 구현하여 결과값을 출력하였습니다.

---

⏱️ 시간 초과

재귀함수를 쓰면 효율성 테스트에서 시간 초과가 발생할 것이라 예상했는데
역시나 시간초과가 발생하였습니다.
getAn() 메서드에서 반환값으로 재귀 호출하는 부분에서 중복되는 n이 많을 것이라 예상되었습니다.
그래서 그것을 일일이 다시 계산하지 않고 이미 한번 호출했던 n에 대해서는 값을 바로 가져올 수 있도록
인스턴스 변수로 Map<Long, Long> An을 선언하고 An에서 값을 추가 및 조회하도록 코드를 변경하였습니다.

---

📑제출 기록 및 오답 원인

중간에 import를 빼먹어서 한번 컴파일 에러가 발생했지만 성공적으로 제출하였습니다.

---

💯 해결 방법

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

public class Main {
    public static Map<Long, Long> An;
    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());
        long P = Long.parseLong(st.nextToken());
        long Q = Long.parseLong(st.nextToken());
        An = new HashMap<>();

        System.out.println(getAn(N, P, Q));
    }

    public static long getAn(long n, long p, long q) {
        if (n == 0) {
            return 1;
        }

        long sub1 = n / p;
        long sub2 = n / q;
        long Asub1;
        long Asub2;

        if (An.containsKey(sub1)) {
            Asub1 = An.get(sub1);
        } else {
            Asub1 = getAn(sub1, p, q);
            An.put(sub1, Asub1);
        }

        if (An.containsKey(sub2)) {
            Asub2 = An.get(sub2);
        } else {
            Asub2 = getAn(sub2, p, q);
            An.put(sub2, Asub2);
        }

        return Asub1 + Asub2;
    }
}