[BOJ] 1629 - 곱셈 (Java)

알고리즘

• 수학
• 분할 정복을 이용한 거듭제곱

1. 문제

2. Idea

• "분할 정복"을 사용하여 A^B mod C를 구해야 함.

  분할 정복(Divide and Conquer)

  • 큰 문제를 작은 단위의 문제로 나누어 해결하고, 그 해답을 합쳐서 전체 문제의 해답을 얻는 알고리즘 설계 기법

  1. 분할(Divide): 원래의 문제를 작은 크기의 동일한 문제들로 나눈다. 보통 문제를 반으로 쪼개거나, 고르게 나눌 수 있는 다른 방법을 사용한다.
  2. 정복(Conquer): 작은 문제들을 재귀적으로 해결한다. 만약 작은 문제의 크기가 충분히 작다면, 재귀를 멈추고 문제를 풀 수 있는 직접적인 방법을 사용한다
  3. 결합(Combine): 작은 문제들의 해답을 결합하여 원래 문제의 해답을 구한다.

3. 풀이

3.1. 변수 입력

• A, B, C 입력

long A = in.nextLong();
long B = in.nextLong();
C = in.nextLong();

3.2. pow 함수 구현

• A의 exponent 거듭제곱 값을 반환
• if
  exponent가 1이라면, A^1=A이므로 AmodC 값을 반환
• else
  • (exponent가 홀수인 경우)
    • A^(2k+1)이므로 재귀적으로 계산하여 계산 횟수를 줄여나감.
    • A^(2k+1)=A^kA^kA 임을 이용
  • (exponent가 짝수인 경우)
    • A^2k=A^k*A^k 임을 이용

public static long pow(long A, long exponent) {
	
	if(exponent == 1) {
		return A % C;
	}
	long temp = pow(A, exponent / 2);

	if(exponent % 2 == 1) {
		return (temp * temp % C) * A % C;
	}
	return temp * temp % C;
}

3.3. 함수 호출 및 결과 출력

System.out.println(pow(A, B));

4. 전체코드

import java.util.Scanner;
 
public class Main {
 
	public static long C;
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		
		long A = in.nextLong();
		long B = in.nextLong();
		C = in.nextLong();
		System.out.println(pow(A, B));
	}
	
	public static long pow(long A, long exponent) {
	
		if(exponent == 1) {
			return A % C;
		}
		long temp = pow(A, exponent / 2);

		if(exponent % 2 == 1) {
			return (temp * temp % C) * A % C;
		}
		return temp * temp % C;
	}
}