[백준 1주차 - 1629] 곱셈 (Java)

📌문제

 

 

📝 풀이과정

단순히 for문을 이용해서 A를 B번 곱한 다음, 나머지를 출력하면 될까?

문제를 볼 때 가장 먼저 입력의 최대, 최소 범위를 봐야 한다

여기서 최대 범위는 20억인데, for문으로 A를 B번 곱하게 되면 즉 시간 복잡도는 20억이 된다

 

그렇다면 어떻게 접근해야 할까?

'모듈러 연산'과 '지수법칙'으로 접근하면 된다

 

모듈러 연산

 

모듈러 식을 연산자를 이용하여 표현해보면

 

→ 문제에서 최대범위로 계산 했을 때 A(20억)을 B(20억) 번 계산해야 한다 그렇게 되면 long long의 범위를 벗어나고 오버플로가 발생하게 된다 따라서 A를 C로 나누면서 곱하는 식으로 계산해야 한다

 

 

 

 

지수법칙

 

2를 8번 곱하면 연산 횟수가 많다

따라서 지수법칙에 따라 2^4를 하나의 변수 K에 넣고  K * K의 연산을 수행하면서 지수가 1일때 까지 지수를 반으로 나누어서 반복한다 그러면 3번의 반복으로 연산횟수가 줄게 된다

 

→ 시간복잡도 20억에서 log2의 20억으로 시간복잡도를 줄일 수 있다

 

 

💻 코드

import java.util.*;
import java.io.*;
public class Main{
	public static long c;
	public static void main(String[]args)throws IOException{
		long a,b;
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		
		a=Long.parseLong(st.nextToken());
		b=Long.parseLong(st.nextToken());
		c=Long.parseLong(st.nextToken());
		
		System.out.println(pow(a,b));
	}
	
	public static long pow(long a,long b){
		if(b==1){//지수가 1이면
			return a%c; 
		}			
		long ret=pow(a,b/2); //지수법칙 적용
		
		//모듈러 법칙 적용
		if(b%2==1) return (ret*ret%c)*a%c; //지수가 홀수라면 a를 더 곱해준다
		return (ret*ret)%c; 
	}
}