[BOJ 1354] 무한 수열2 - JAVA, Gold5

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

1354번: 무한 수열 2

사용한 알고리즘 : Map 데이터 구조를 사용한 풀이

 

풀이 전략

Map 데이터구조를 이용하여 이미 구해놓았던 값은 다시 연산하지 않도록 했다.

static Map<Long,Long> map = new HashMap<>();  // 전역 변수로 선언되어있음

map.put(0L,1L); // main 함수에서 정의되었음

static long func(long num){
    if(map.containsKey(num)) return map.get(num);
    if(num<=0) return 1;

    long first = func(num/P-X);
    long secont = func(num/Q-Y);

    map.put(num,first+secont);
    return first+secont;
}

func 메소드에 우리가 구하고 싶은 N 값을 매개변수로 입력하면,

 

해당 매개변수를 키로 갖고 있는 노드가 있다면 값을 반환,

없다면 재귀를 통해 Anum = A⌊num/P⌋-X + A⌊num/Q⌋-Y (num ≥ 1) 을 구해 값을 계산한다.

 

그러면 기존에 구했었던 key 값에 대해서는 다시 연산하지 않고

이전에 연산했던 값을 반환해주어 연산의 수가 줄어든다.

 

제출코드

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

public class Main{
    static long N,P,Q,X,Y;
    static Map<Long,Long> map = new HashMap<>();
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Long.parseLong(st.nextToken());
        P = Long.parseLong(st.nextToken());
        Q = Long.parseLong(st.nextToken());
        X = Long.parseLong(st.nextToken());
        Y = Long.parseLong(st.nextToken());

        map.put(0L,1L);
        func(N);
        bw.write(map.get(N)+"\n");
        bw.flush();
        bw.close();
    }

    static long func(long num){
        if(map.containsKey(num)) return map.get(num);
        if(num<=0) return 1;

        long first = func(num/P-X);
        long secont = func(num/Q-Y);

        map.put(num,first+secont);
        return first+secont;
    }
}