[ Baekjoon ] 1629번 - 곱셈

1629번: 곱셈

 

풀이 방법

지수를 나누어 재귀로 푸는 것이 이 문제의 핵심이다.

다른 코드들을 살펴보면 함수 전달 시 A인자에 A%C를 전달해 주는 경우가 있다. 이 부분이 이해가 안가서 찾아보던 중 함수 안에서 if (B == 1) return A % C; 이와 같은 제약조건을 준다면 그냥 A를 전달해주어도 된다.

 

구현 코드

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

public class Q_1629 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		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(divide(A, B, C));
	}
	
	// 첫번째 방법
	public static long divide(long A, long B, long C) {
		if (B == 0) return 1;
		if (B == 1) return A % C;
		
		long divide2 = divide(A, B/2, C); // 지수를 2로 나누기
		
		if (B % 2 == 0) { // 지수가 짝수이면
			return divide2 * divide2 % C;
		} else { // 지수가 홀수이면
			return (divide2 * divide2 % C) * A % C; // divide2 * divide2 * A % C -> long 범위 초과
		}
	}
	
	// 두번째 방법
	public static long divide_1(long A, long B, long C) {
		if (B == 0) return 1;
		if (B == 1) return A % C;
		
		if (B % 2 == 0) { // 지수가 짝수이면
			long divide2 = divide_1(A, B/2, C); // 지수를 2로 나누기
			return divide2 * divide2 % C;
		} else { // 지수가 홀수이면
			return divide_1(A, B-1, C) * A % C;
		}
	}
}