[백준] 1351번 : 무한 수열 – JAVA [자바]

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

1351번: 무한 수열

 

---

• 문제

 

 

---

• 문제 풀이

백준 1351번 무한 수열은 골드 5 난이도의 DP 및 해시 문제이다. 이 문제 자체는 되게 간단하다. 3개의 정수 N, P, Q가 주어지고 아래에 있는 공식을 써서 An을 구하면 된다.

 

 

이 문제에서는 참고해야 할 게 있다. 우선 정수 N의 범위 0 ≤ N ≤ 10^12이다. 즉, 이 범위는 long 형이고 자바에서는 배열이 long 형인 크기로 만들지 못한다. 자세한 이유는 이 링크를 참고하면 되겠다. 즉, 값들을 배열에 저장을 할 수가 없기 때문에 해시맵에 저장해야 한다.

 

추가로, 이 문제는 Bottom-Up 방식을 이용해서 풀면 메모리 초과가 뜨기 때문에 Top-Down, 즉 재귀를 이용해서 풀어야 한다. 이게 뭔지 잘 모른다고 이 링크를 참고하면 되겠다. Bottom-Up 방식을 이용했을 때 메모리 초과가 뜨는 이유는 1부터 N까지 모든 값들을 계산하고 저장하기 때문이다. 하지만 Top-Down 방식을 이용했을 때는 필요한 값들만 계산하고 저장하기 때문에 더 효율적일 수 있다.

 

이 점들을 참고하면 문제를 푸는 것은 크게 어렵지 않다. 우선 해시맵에 (0, 1)을 저장한다. 그리고 재귀 방식을 이용하려면 함수를 새로 만들어야 하는데 이 함수를 find()라고 하겠다. 

 

find() 함수는 되게 간단하다. 우선 해시맵의 키인 long n을 매개변수로 받고, 이 맵에 키가 n인 값이 있으면 반환하고 없으면 문제에서 주어진 공식을 이용해서 값을 계산하고 다시 맵에 저장하고 이 값을 변환하면 된다.

 

자세한 코드는 아래에 있는 코드를 참고하면 되겠다.

 

 

---

• 코드

 

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    static Map<Long, Long> map = new HashMap<>();
    static long n;
    static long p;
    static long q;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Long.parseLong(st.nextToken());
        p = Long.parseLong(st.nextToken());
        q = Long.parseLong(st.nextToken());
        map.put(0L, 1L);
        find(n);
        System.out.println(map.get(n));
    }

    public static long find(long n) {
        if (map.containsKey(n)) return map.get(n);
        long first = find((long)Math.floor(n/p));
        long second = find((long)Math.floor(n/q));
        map.put(n, first+second);
        return first + second;
    }

}