[백준] 1351 무한수열 - Java

 

 

 

해시 맵으로 메모이제이션을 수행해 풀 수 있는 문제이다.

재귀를 제대로 이해했고, 입력의 타입만 잘 맞춰주면 쉽게 풀 수 있다.

 

import java.util.*;
import java.io.*;
public class Main041{

    static Long P;
    static Long Q;
    static Long N;
    static HashMap<Long, Long> hm;
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Long.parseLong(st.nextToken());
        P = Long.parseLong(st.nextToken());
        Q = Long.parseLong(st.nextToken());

        hm = new HashMap<>();

        long ans = solve(N);

        System.out.println(ans);


        
    }
    static long solve(long i){

        if(i == 0){
            return 1;
        }

        if(hm.containsKey(i)){
            return hm.get(i);
        }

        hm.put(i, solve(i / P) + solve(i / Q));

        return hm.get(i);
    }
}

 

1354번 문제도 위 문제와 동일한 문제이다.

복습할 겸 같이 풀어보자!