[BaekJoon] 1351 무한 수열

1.  문제 링크

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

2.  문제

요약

• 무한 수열 A는 아래와 같습니다.
  • $A_0 = 1$
  • $A_i = A_{⌊i/P⌋} + A_{⌊i/Q⌋}$(i ≥ 1)
• N, P와 Q가 주어질 때, $A_N$을 구하는 문제입니다.
• 입력: 첫 번째 줄에 0보다 크거나 같고 $10^{12}$보다 작거나 같은 N, 2보다 크거나 같고 $10^9$보다 작거나 같은 P, Q가 주어집니다.
• 출력: 첫 번째 줄에 $A_N$을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;

public class Main {
	HashMap<Long, Long> map;
	public long getNthNum(long num, int p, int q) {
		if(num == 0)
			return 1;
		if(map.containsKey(num))
			return map.get(num);
		long left = num / p;
		long right = num / q;
		map.put(num, getNthNum(left, p, q) + getNthNum(right, p, q));
		return map.get(num);
	}
	
	public long getInfiniteSequence(long n, int p, int q) {
		map = new HashMap<>();
		return getNthNum(n, p, q);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		br.close();
		long n = Long.parseLong(input[0]);
		int p = Integer.parseInt(input[1]);
		int q = Integer.parseInt(input[2]);
		Main m = new Main();
		bw.write(m.getInfiniteSequence(n, p, q) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 DP를 이용하여 구할 수 있는 문제입니다.
• 각 계산 과정에서 나오는 값들은 HashMap을 이용하여 저장합니다.
• 예를 들어, $A_i$에 대한 값은 i라는 key에 $A_{⌊i/P⌋} + A_{⌊i/Q⌋}$을 계산한 값이 value로 map에 들어가게 되어 $A_i$ 값을 나타냅니다.
• N부터 시작하여 해당 값을 P로 나눈 값과 Q로 나눈 값에 대해 재귀함수를 통해 각 값들을 구해주고 이를 더하여 $A_N$을 찾습니다.
• 재귀함수를 통해 $A_0$ 이후부터 각 값들을 찾아 map에 저장하게 되고 이렇게 저장된 이전 값들을 이용하여 다음 값을 구하는 데에 사용하기 때문에 메모이제이션을 이용합니다.

1. 무한 수열 A들의 값들을 저장하기 위한 HashMap을 생성합니다.
2. 재귀함수 호출을 통하여 $A_N$ 값을 구합니다.
   1. 만약 num이 0이라면, $A_0$ 값인 0을 반환합니다.
   2. 만약 map에 있는 key들에 num이 이미 존재한다면 $A_{num}$ 값을 반환합니다.
   3. 위 두 경우 모두 아니라면 $A_{⌊num/P⌋}, A_{⌊num/Q⌋}$을 구해야 $A_N$을 구할 수 있으므로 left 변수에 num / P를, right 변수에 num / Q를 넣어 변수를 생성합니다.
   4. num이라는 key에 $A_{⌊num/P⌋} + A_{⌊num/Q⌋}$ 값을 value로 하여 $A_{num}$ 값을 HashMap에 표현해줍니다.
   5. 4번에서 $A_{⌊num/P⌋} + A_{⌊num/Q⌋}$ 부분은 $A_{⌊num/P⌋}$에 대해서는 left를 num으로 하여 재귀함수를 호출하고, $A_{⌊num/Q⌋}$는 right를 num으로 하여 재귀함수를 호출해서 각 값들을 구해줍니다.
   6. 5번까지의 과정이 모두 끝나 $A_N$ 값을 구했다면 해당 값을 반환합니다.
3. 2번에서 반환된 값이 $A_N$의 값이므로 이를 출력합니다.