[백준 - 1351][GOLD 5][해설 X] - 무한 수열 (JAVA)

문제 링크

---

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

 

문제

---

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

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

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

 

 입력

---

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

 

출력

---

첫째 줄에 AN을 출력한다.

 

해결 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static Map<Long,Long> aMap = new HashMap<>();	//DP 테이블
    private static long N;
    private static int P,Q;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Long.parseLong(st.nextToken());
        P = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());
		
        //A0값 대입
        aMap.put(0L,1L);

        System.out.println(getASequence(N));
    }
	
    //Ai = Ai/P + Ai/Q를 구하는 메소드
    public static long getASequence(long i){
    	//Ai값이 이미 있으면 바로 값 출력
        if(aMap.get(i) != null){
            return aMap.get(i);
        }
		
        //Ai/P 연산
        Long aip = aMap.get(i/P);

        if(aip == null){
            aip = getASequence(i/P);
        }


        //Ai/Q 연산
        Long aiq = aMap.get(i/Q);

        if(aiq == null){
            aiq = getASequence(i/Q);
        }

        aMap.put(i,aip+aiq);

        return aMap.get(i);
    }
}

 

실행 결과

---

 

팁

---

• DP 테이블을 만들 때 크기가 어렵다면 Map을 이용해 만들자
• 입력값이 long인지 int인지 확인하자