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

▶ 문제

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

1629번: 곱셈

 

▶ 설명

 

문제에서 주어진 A,B,C의 범위는 int형의 최대값이기 때문에 pow 메소드를 서서 한 번에 거듭제곱 연산을 처리하려면 시간 초과가 날 수 있다. 지수의 법칙과 모듈로에 대한 이해를 한 다음에 다시 이 문제에 접근하면 짧은 시간안에 결과 값을 얻어낼 수 있다.

 

 

지수 법칙

(출처 : mathfactory  )

 

 

 

모듈로 곱셈

(출처 : khan  )

 

 

모듈로 연산 연습해보기 ↓

(702⋅398) mod 20 의 답은 > 16 

(출처 : khan  )

 

문제로 다시 돌아가보자.

예제를 살펴보면, 지수의 법칙에 의해서 10^11 은 10^5와 10^6으로 쪼갤 수 있다.

①  10^11%12 = (10^5 x 10^6) %12 

 

그리고 모듈로 곱셈의 성질에 의해서 12로 나눈 나머지를 구하는 연산을 다시 재구성할 수 있다.

② (10^5 x 10^6) %12 = ((10^5%12) x (10^6%12)) %12 

위 식에서  (10^5%12) 는 ①에서 10^11%12 의 식을 둘로 쪼갠 것 처럼 분리할 수 있다.

 

계속 쪼개다가 지수가 1이 될 때  (10^1%12) 나머지를 구하는 연산을 수행하면 부분을 합쳐 전체를 이루는 결과 값을 얻어낼 수 있게 된다.

 

 

주의할 점

 

     1.  지수가 홀수일 경우와 짝수일 경우에 다르게 처리해줘야 한다.

 

①번의 연산 과정 처럼 지수법칙에 의해 두 수로 나누게 되는데 이때 절반으로 나누어야 하지만 지수가 홀수일 경우는 1이 남게 된다. 

- 지수가 홀수일 때 : 10^11%12 = (10^5 x 10^6) %12   →  ((10^5 x 10^5) %12 ) x (10^1%12)

11을 2로 나누었을 때 나머지가 발생하면 위의 식 처럼 10%12 을 곱하는 연산에 추가해 주어 같은 지수로 2개를 맞춰준다.

지수를 같게한 이유는 연산의 반복을 줄일 수 있기 때문이다.

 

- 지수가 짝수일 때 : 10^12%12 = (10^6 x 10^6) %12 

 

 

     2. 피연산자를 저장하는 변수는 long형이어야 한다.

 

2147483647 ^ 2 %1073741824

라는 연산을 수행해야 한다고 하면, 연산 과정에서 int형의 범위를 넘길 수 있으므로 long형으로 맞춰 주어야 한다.

과정 1 : 2147483647 ^ 2 %1073741824 = (2147483647  ^ 1 x 2147483647 ^ 1)%1073741824 

과정 2 :  (2147483647  ^ 1 x 2147483647 ^ 1)%1073741824 

             =   ((2147483647  ^ 1 %1073741824 )  x 2147483647 ^ 1 %1073741824 )%1073741824 

과정 3 : ((2147483647  ^ 1 %1073741824 )  x 2147483647 ^ 1 %1073741824 )%1073741824 

             =  (1073741823 x 1073741823 )% 1073741824 

                └ int형으로 연산 불가!! 

int 형의 max 범위 : 2,147,483,647

long 형의 max 범위 : 9,223,372,036,854,775,807

 

 

 

 

 

 

▶ 문제 풀이

🌱 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public 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(remainder(a, b, c));
	}

	private static long remainder(long a, long b, long c) {
		// 지수가 1이면 바로 나머지 구하기.
		if (b == 1) {
			return a % c;
		}
		// 지수가 1 이상이면 지수를 반으로 나누어 다시 나머지 구하기.
		else {

			long halfVal = remainder(a, b / 2, c);
			// 지수가 홀수일 때
			if (b % 2 == 1) {
				return (halfVal * halfVal % c) * a % c;
			}
			// 지수가 짝수일 때
			return halfVal * halfVal % c;
		}
	}
}

 

 

 

 

 

▶ Log

거듭 제곱을 분할정복으로 풀 수 있다는 점이 낯설었지만 흥미로운 접근이라 생각되었다.

이 문제를 기회 삼아 나머지 연산에 대한 성질과 지수법칙에 대해 한 번 더 짚고 넘어가봐야 겠다.