❔ 문제
무한 수열 A는 다음과 같다.
- A0 = 1
- Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1)
N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 3개의 정수 N, P, Q가 주어진다.
출력
첫째 줄에 AN을 출력한다.
제한
- 0 ≤ N ≤ 1012
- 2 ≤ P, Q ≤ 109
예제 입력1
7 2 3예제 출력1
7예제 입력2
0 2 3예제 출력2
1예제 입력3
10000000 3 3예제 출력3
32768예제 입력4
256 2 4예제 출력4
89예제 입력5
1 1000000 1000000예제 출력5
2🔍 문제 풀이
이 문제는 AN을 구하기 위해 AN/P 와 AN/Q값을 계속해서 참조해야하는 문제이다.
1. 재귀 함수 활용
- AN을 구하는 함수
solution(n)생성 - 이미 계산된 값이 있다면, 저장된 값을 반환
- 없다면, AN = AN/P + AN/Q 을 재귀적으로 계산하여 저장
2. 해시맵(HashMap) 활용
- 해시맵을 사용하여 이미 계산된 값을 저장하고 불필요한 중복 계산 방지
☑️ 최종 코드
import java.io.*;
import java.util.*;
public class Main {
static long n;
static long p;
static long q;
static HashMap<Long,Long> map = new HashMap<>();
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
n = Long.parseLong(input[0]);
p = Long.parseLong(input[1]);
q = Long.parseLong(input[2]);
map.put(0L, 1L);
System.out.println(solution(n));
}
static long solution(long n) {
if (!map.containsKey(n)) {
map.put(n,solution(n / p) + solution(n / q));
}
return map.get(n);
}
}
