백준 1629 자바

이전에 풀었을 때

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.util.Collections;
public class Main{
    public static long  DivideMulti(int A,int B,int C){
        if(B==0){
            return 1;
        }
        if(B%2!=0){
            return A*(DivideMulti(A,B-1,C)%C)%C;
        }
        else{
            long tmp=DivideMulti(A,B/2,C)%C;
            return (tmp*tmp)%C;
        }
    }
    public static void main(String[] args) {
         Scanner scanner=new Scanner(System.in);
         int A= scanner.nextInt();
         int B=scanner.nextInt();
         int C= scanner.nextInt();
        System.out.println(DivideMulti(A,B,C)%C);
    }

}

현재 풀었을 때

결국 예전에 풀었던 것을 참조했다.(이게 맞니?)

왜 못풀었던 것일까?

시간초과-1

보자마자 생각난 것은 Math.pow 로 계산하는 것이였지만
난 이게 시간 복잡도가 그대로 곱하는 갯수만큼 그대로 비례해서 증가하는줄 몰랐다(O(n))

시간초과-2(틀린 풀이)

위 내용을 깨닫고 분할정복을 시작했다.
분할 정복이니까...

오랜만에 풀어서 그런지 분할 정복의 이점을 살리지 못했다.

import java.lang.reflect.Array;
import java.util.*;
import java.util.Collections;
public class Main{
    public static long  DivideMulti(int A,int B,int C){
        if(B==0){
            return 1;
        }
        if(B%2!=0){
            return A*(DivideMulti(A,B-1,C)%C)%C;
        }
        else{
            long tmp=DivideMulti(A,B/2,C)%C;
            return (tmp*tmp)%C;
        }
    }
    public static void main(String[] args) {
         Scanner scanner=new Scanner(System.in);
         int A= scanner.nextInt();
         int B=scanner.nextInt();
         int C= scanner.nextInt();
        System.out.println(DivideMulti(A,B,C)%C);
    }

}

이 내용은 분할 정복을 이용해서 풀긴했지만 결국 모든 지수 승을 계산한다는 단점이 있었다. 결국 맨 밑에 내려가면 a*a가 최대 10^9 의 만큼의 연산을 할 가능성이 있기에 시간 0.5초에는 한참 못미친다.

우리의 목표는 계속 반으로 줄이는 것이다.

틀린 이유

또한 모듈러 공식의 존재에 대해 잊고 있었다.

이렇게 공식을 사용하면 얻는 이점은

예를 들어 (a*b) 가 long 의 범위를 넘어가면 저런식으로 사용할 수 있다는 소리이다.

나머지값을 계산할 때는 항상 모듈러 공식을 생각을 하자.

정답

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {



    public long divide(int a,int b,int c){
        if(b==1){
            return a;
        }
        else if(b==0){
            return 1;
        }
        else{
            long mediumCal=divide(a,b/2,c)%c;

            if(b%2!=0){
                return a*(mediumCal*mediumCal%c);
            }
           return (mediumCal*mediumCal)%c;
        }
    }
    public void solution() throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));



        StringTokenizer st = new StringTokenizer(br.readLine());

        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());



        System.out.println((divide(a,b,c)%c));




    }


    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}