백준 [java 자바] 1629번 : 곱셈

이 문제는 정말 오랜만에 혼자 해결하지 못한 문제입니다. 아무리 풀어도 답이 나오지 않아서 다른 블로그 글을 참고했고 덕분에 분할 정복에 대해 알게 되었습니다.

언뜻 보기에는 쉬워 보이지만 사실 굉장한 장애물이 있습니다. 바로! 입력받은 수를 곱하면 long자료형이어도 넘어갈 수 있다는 것이다. 그래서 내가 다른 방법으로 풀었을 때 방법은 맞지만 틀렸습니다가 나온 이유인 것 같다. 

 이 문제에서 가장 중요한 개념은 거듭제곱을 분할하는 것 그러니까 10^5 = 10^2 * 10^2 * 10 이렇다는 것을 이용하는 것이다. 

 그리고 (a*a)% c와 (a% c)*(a% c)% c는 같다는 것이다. 근거는 (a*c + b)*(a*c+b) 하고 c로 나누어주면 어차피 남는 것은 b*b이기 때문이다.

package cah3.ex1;


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


class Main{
	
 public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    long a = Long.parseLong(st.nextToken());

    long b = Long.parseLong(st.nextToken());

    long c = Long.parseLong(st.nextToken());

    
    System.out.println(re(a,b,c)%c);
    
    }
 
 static long re(long a, long b, long c) {
	 if(b== 1) return(a%c);
	 
	 long now = re(a,b/2,c);
	 
	 if(b %2 == 0) {
		 return (now*now%c);
	 }
	 else {
		 return (now*now%c*a%c);
	 }
	 
 }
 }

여기서 실수했던 점은 마지막 줄에 now*now를 c로 나눈 수와 a를 c로 나눈 수를 곱해서 나눴다는 것이다. 이렇게 하면 long값보다 큰 값이 리턴되어 틀린 답이 나올 수 있다.

 

알아야 할 점

 거듭제곱은 분할 정복을 사용하자

 위의 수학공식

 자료형 넘어가는 것을 유의하자