[백준] 1351 무한수열

문제보기

N의 범위가 상당히 크기 때문에, 일반적인 dp로 메모이제이션 하며 해결하기에는 메모리가 터져버린다. 사실 생각해보면 N/P, N/Q는 연속적이지 않으므로 (P, Q >= 2) 메모이제이션 될 배열의 원소가 N개가 되는건 상당히 낭비적이다.
따라서 HashMap을 써주면서 DP로 가주면 된다!!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

class Main{
	static int p;
	static int q;
	static HashMap<Long, Long> map;
	
	static long go(long n) {
		// 첫 항은 1이라고 주어졌다. 
		if( n == 0 ) return 1;
		// 메모된 값이 있다면 그걸 쓰자 
		if(map.containsKey(n)) {
			return map.get(n);
		}
		// 없다면 직접 구해주자~!!
		map.put(n, go(n/p) + go(n/q));
		
		// 반환한다 
		return map.get(n);
	}
	
     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());
    	p = Integer.parseInt(st.nextToken());
    	q = Integer.parseInt(st.nextToken());
    	
    	map = new HashMap<Long, Long>();
    	
    	System.out.println(go(n));
    	
     }
}