1351 : 무한 수열

이번 문제는 동적 프로그래밍 문제이다

Memoization 기법이 기억이 잘 안나서 한참 걸림.

다행히도 숫자가 Integer 범위를 벗어나는 것과 Memory 초과 오류밖에 나지 않았다

Memo를 해야할 자료구조를 Hash로 쓰는게 핵심이었다.

저번 문제에서도 배열이나 List를 사용하던 중 인덱스 번호로 배열 원소에 접근하려고 하다가 시간초과가 난 적이 있었는데, Hash로 그런 문제를 해결할 수 있는 것 같다.

 

import java.util.*;
import java.util.stream.Stream;
import java.io.*;

public class Main {
	static int P;
	static int Q;
	static HashMap<Long, Long> map = new HashMap<Long, Long>();
	
	public static long Solve(long i) {		
		if(i==0) {			
			return 1;
		} else {
			if(map.get(i)==null) {
				long number=Solve(i/P)+Solve(i/Q);
				map.put(i, number);
				return number;	
			} else {
				return map.get(i);
			}
		}
	}
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		long[] input = Stream.of(br.readLine().split(" ")).mapToLong(Long::parseLong).toArray();

		long N = input[0];
		P = (int) input[1];
		Q = (int) input[2];

		map.put((long)0, (long) 1);
			
		bw.write(String.valueOf(Solve(N)));	
		bw.flush();
		bw.close();
	}
}