Softeer 슈퍼바이러스 (Lv3)

문제

https://softeer.ai/practice/info.do?idx=1&eid=391&sw_prbl_sbms_sn=140793

알고리즘

위 문제를 해석해보면 K x P^10N 을 구하는 문제인 것을 확인할 수 있다.
그러나 시간 복잡도가 O(N)인 for문 하나로 K x P^10N을 풀게 되면 시간 초과가 나오게 된다. 그 이유는 총 시간 N의 범위가 10^16까지이기 때문이다.

시간 초과를 안 하기 위해서는 O(log N) 시간 복잡도를 갖는 재귀 함수를 통해 풀어야 한다.

코드

import java.util.*;
import java.io.*;
/*
 * 2023.02.03
 * 수퍼바이러스
 * long의 최대값이 10^19라고한다.
 * half * half * p의 순간 최대값은 10억 * 10억 * 1억.... 
 *  (half * half % 1000000007) 이렇게 고쳐줬더니 드디어 풀림
 */
public class Main
{    
    static int MOD = 1000000007;
    public static void main(String args[]) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int K = Integer.parseInt(st.nextToken());   // 바이러스 수
        int P = Integer.parseInt(st.nextToken());   // 증가율
        long N = Long.parseLong(st.nextToken());   // 총 시간

        System.out.println(K * calc(P, 10*N) % MOD);
    }

    public static long calc(int P, long N) {
        if(N==1) return P;

        long half = calc(P, N/2);

        if(N%2 == 0){
            return half * half % MOD;
        } else {
            return (half * half % MOD) * P % MOD;
        }
    }
}

배운 점

시간 초과 문제 때문에 애를 많이 먹었다.
알고리즘 문제풀이에서 언제나 가장 중요한 것은 log로 만드는 것. 명심 또 명심.
범위에 조심하자!!
(+ long 값을 int로 입력 받지 말자!! -> Long.parseLong(st.nextToken()); )