[Java] 백준 1629.곱셈

➡️문제 링크

https://www.acmicpc.net/problem/1629

 

 

💡아이디어

분할정복

이라고 지피티의 도움을 받았습니다^^

주어진 조건 "A, B, C는 모두 2,147,483,647 이하의 자연수"을 보고

Math.pow(A, B)를 이용해서 실제로 A^B를 구해 푸는 문제는 아니라고 판단했다.

그런데 그 후로 어떻게 해야하는지 아이디어가 안 나왔다.

처음에는 약수를 구해서 나눠야 하나 싶다, 그러면 결국 남은 수들을 곱해야하니까 의미가 없고..

그래서 결국 지피티에게 물어봐

분할정복이라는 아이디어를 얻게 되었다.

 

 

우리가 구해야 하는 건 첫 번째 수식이다.

A^B는 A를 B번 곱했기 때문에 (a*b)로 표현할 수 있다.

그렇다면, 마지막 줄 처럼 첫 번째 수식을 표현할 수 있다.

 

A = 3, B = 5, C = 7 일때의 과정이다

값을 곱할때마다 %7을 하더라도 결과는 변하지 않는다는 것을 확인할 수 있다

 

 

✏️문제 풀이

1. 분할정복 -  성공(지피티 참고)

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// 입력
		long A = Integer.parseInt(st.nextToken());
		long B = Integer.parseInt(st.nextToken());
		long C = Integer.parseInt(st.nextToken());
		
		System.out.println(solve(A, B, C));
		
	}
	
	static long solve(long A, long B, long C) {
		if(B == 1) return A % C;
		
		long tmp = solve(A, B/2, C);
		
		if(B %2 == 0) {
			return (tmp*tmp) % C;
		}else {
			return ((tmp * tmp) % C * A) % C;
		}
	}

}