백준 1629번 곱셈 문제

ㅋㅋㅋㅋ 단순 곱셈하고 나누는 문제있은 줄 알고 문제 그대로 곱하고 나누는걸 그냥 반복문 돌렸는데 역시나 시간 초과.....

 

시간 복잡도를 줄여야 했다.. 고로 사용한 것이 분할 정복 알고리즘이다.. 

 

위 식을 사용 하여야 했다.. 참고해서 코드를 만들어 봤다..

그리고 문제에서 abc 모두 자연수가 2147483647이라 int형으로 했는데 연산하는 과정에서 이 범위를 초과함으로 long형태로 변수를 만들어 주었다.

package codetest;

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // Scanner 대신 사용 사용이유 앞 블로그에서 설명함

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

		long a = Long.parseLong(st.nextToken()); // bufferreder는 string형태로 받아오기때문에 long형으로 변환		
		long b= Long.parseLong(st.nextToken()); // bufferreder는 string형태로 받아오기때문에 long형으로 변환		
		long c = Long.parseLong(st.nextToken()); // bufferreder는 string형태로 받아오기때문에 long형으로 변환
	
		System.out.println(cal(a,b,c)%c);//a를 b번 곱한수를 c로 나눈 나머지
	}

	static long cal(long a, long b, long c) {
        if (b == 0) {
            return 1;
        } else if (b == 1) {
            return a;
        } else if (b % 2 == 0) { //짝수
            long n = cal(a, b / 2, c) % c; //재귀호출로 나눔
            return (n * n) % c;//n의n제곱함
        } else { //홀수
            long n = cal(a, b / 2, c) % c;//재귀호출로 나눔
            return (((n * n) % c) * a) % c;
        }
	}
	
}