[Algorithm] 99클럽 코테 스터디 25일차 TIL | 백준_무한 수열(1351번)

📝문제

 

💡풀이

N의 크기가 10¹² 까지 허용된다는 점이 이 문제의 킥이다.

처음엔 반복문으로 풀어 메모리 초과가 났었다.

 

재귀문을 사용하여 풀면 기존 O(N)에서 O(logN)으로 시간복잡도를 향상시킬 수 있다.

 

solve(7)

solve(7/2=3)+solve(7/3=2)

solve(3/2=1)+solve(3/3=1)+solve(2/2=1)+solve(2/3=0)

solve(1/2=0)+solve(1/3=0)+solve(1/2=0)+solve(1/3=0)+solve(1/2=0)+solve(1/3=0)+solve(0)

 

위와 같이 한 번의 호출에서 최대 두 번의 호출이 발생하고 solve(0)을 만나면 1을 반환해주는 방식을 사용한다.

 

전체 풀이

import java.util.*;
import java.io.*;
class Main{
    static long N,P,Q;
    static HashMap<Long, Long> map;
    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 = new HashMap<>();
        map.put(0L, 1L);

        System.out.println(solve(N));
    }
    public static long solve(long i){
        if(map.containsKey(i)){
            return map.get(i);
        }
        long result = solve(i/P) + solve(i/Q);
        map.put(i, result);
        return result;
    }
}

 

🤔Review

풀고 나니 별거 아닌 거 같은 코드지만 생각해내기 넘 어려웠다,,재귀문은 구현할 때마다 헷갈리는 거 같다ㅜ dp문제들을 더 연습해야겠다