[BOJ] 백준 1351번 무한 수열 (Java)

#1351 무한 수열

난이도 : 골드 4

유형 : DP

1351번: 무한 수열

▸ 문제

무한 수열 A는 다음과 같다.

• A0 = 1
• Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1)

N, P와 Q가 주어질 때, An을 구하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 3개의 정수 N, P, Q가 주어진다.

▸ 출력

첫째 줄에 An을 출력한다.

 

문제 풀이

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

📚 조건

   ∙ 0 <= N <= 10^12

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

 

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

 

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

 

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

 

풀이 코드 

import java.io.*;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {

//	static long[] dp;
	static Map<Long, Long> map = new HashMap<>();
	static int p,q;
	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());
		
//		dp = new long[(int) (n+1)];
		
		System.out.println(solve(n));
		
	}
	
	static long solve(long num) {
		
		if(num==0) return 1;
		if(map.containsKey(num)) return map.get(num);
		
		long a= (long)Math.floor(num/p);
		long b= (long)Math.floor(num/q);
		
		map.put(num, solve(a)+solve(b));
		return map.get(num);
//		return dp[(int)num] = solve(a) + solve(b);
	}
}