[소프티어] 수퍼바이러스 자바 풀이 레벨3 분할정복 알고리즘

[소프티어] 수퍼바이러스 자바 풀이 레벨3 분할정복 알고리즘

 

 

 

 

처음 풀면 어려운데, 한번 풀어보고나면 잊을 수 없는 녀석인 것 같다.

 

 

 

 

 

 

 

 

 

 

수퍼바이러스가 괜히 수퍼가 아니더라.

바이러스 문제보다 진화했다.

매 반복문에 % 1000000007 을 하더라도 시간초과 발생

 

10^16이라니

어떻게 풀었는지 확인해보자.

 

 

 

 

문제스펙

 

 

 

핵심 설명

16 = 2^4 = (2^2) * (2^2) 이고,

32 = 2^5 = (2^2) * (2^2) * 2 이다.

그리고 위 연산마다 "%1000000007" 를 적용해주면 컴퓨터가 덜 허덕일 것이다.

 

위의 분할정복 알고리즘을 코드로 구현하자.

 

참고로 half 변수도 한번만 재귀 태워서 계산해주자.

"sol(p, n/2) * sol(p, n/2)" 로 하면 안된다는 의미이다.

 

아맞다..불안하면, 나처럼 매 곱하기 연산마다 %1000000007 를...

 

 

정답코드

import java.io.*;
import java.util.*;

public class Main {

    // public static int n;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        // int n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        Long k = Long.parseLong(st.nextToken());
        Long p = Long.parseLong(st.nextToken());
        Long n = Long.parseLong(st.nextToken());


        // k = k * (p^(10*n))
        // Long pp = 1L;
        // for(long i=0; i<10; i++){
        //     pp = (pp * p) % 1000000007 ;
        // }
        // for(long i=0; i<n; i++){
        //     k = (k*pp) % 1000000007;
        // }

        // k = k * (p^(10*n))
        k = (k * sol(p, 10*n)) % 1000000007;

        bw.write(String.valueOf(k));
        bw.close();
    }

    public static Long sol(Long p, Long n){
        // p^10 = p^5 * p^5
        // p^11 = p^5 * p^5 * p
        if(n==1){
            return p;
        }

        Long half = sol(p, n/2) % 1000000007;
        if(n%2 == 0){
            return (half * half) % 1000000007;
        }else{
            return (half * half) % 1000000007 * p % 1000000007;
        }
    }
}