링크

1351 무한수열

문제

풀이

처음에 dp처럼 풀려고 했지만 배열의 최대 크기는 int 값의 최대 크기와 같아서 n의 범위를 모두 담지 못한다.
그래서 hashMap을 통해 저장하면 된다.

그리고 bottom-up을 통해서 값을 찾으려고 했지만 메모리 초과가 떠버려서 다른사람들의 풀이를 참조했다.

bottom-up은 1부터 n까지 모든 값을 구하는 반면 Top-down방식을 사용해서 문제를 풀면 원하는 값만 뽑아내서 해결할 수 있기 때문에 효율적이다. Top-down은 재귀를 통해 문제를 해결한다.(아직 많이 어렵다)

내 풀이

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


public class Main{
    public static Map<Long, Long> map = new HashMap<>();

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        //n의 크기가 int형을 벗어남. 그리고 배열의 크기는 int형의 최댓값이기 때문에 hash사용하기
        long n = Long.parseLong(st.nextToken());
        int p = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());

        map.put(0L, 1L);
        solved(n, p, q);

        System.out.println(map.get(n));
    }

    public static Long solved(Long number, int p, int q){
        if(map.containsKey(number)) return map.get(number);

        long a = solved(number / p, p, q);
        long b = solved(number / q, p, q);

        map.put(number, a+b);
        return a+b;
    }


}```