백준 1351번: 무한수열 (G5)

문제

https://www.acmicpc.net/problem/1351

---

풀이 방법

문제에서 주어진 점화식을 가지고 DP 메모이제이션 풀이를 하는 문제이다.

📚 조건
∙ 0 <= N <= 10^12

∙ 2 <= P,Q <= 10^9

범위가 너무 커서 당황했다. 처음에 메모이제이션으로 수를 저장해 풀었지만 long값으로 넘어가 배열 저장공간이 초과해 오류가났다.

N값이 너무 커서 모든 부분을 배열에 저장해서 쌓아가면 안된다.

그래서 구글링 후 해결 방법을 찾은 것이 Map이었다. Map<Long, Long>은 범위가 정해져 있지 않아 key값에 따라 value를 저장하기 때문에 범위초과 문제가 없이 공간 활용도를 높여서 잘 해결되었다.

---

코드

package day0206;

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

public class BOJ_G5_1351_무한수열 {
	static long P, Q;
	static Map<Long, Long> map;

	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 = Long.parseLong(st.nextToken());
		Q = Long.parseLong(st.nextToken());
		
		map = new HashMap<>();
		
		System.out.println(calc(N));
	}
	
	public static long calc(long n) {
		if(n==0) return 1;
		
		if(map.containsKey(n)) {
			return map.get(n);
		}
		
		long div1 = (long) Math.floor(n/P);
		long div2 = (long) Math.floor(n/Q);
		
		map.put(n, calc(div1) + calc(div2));
		return map.get(n);
	}
}