[백준] - 1629번: 곱셈(Java)

문제📝

풀이💡

• 제곱이 1인 경우에는 a%c를 한다.
• 지수의 절반 값을 구하고 지수가 홀수인 경우와 짝수인 경우로 나눈다.
• 지수가 홀수인 경우 먼저 나머지를 취하고 계속해서 곱한다.
• 지수가 짝수인 경우 지수의 절반 * 지수의 절반 %c를 한다.

코드💻

// 백준 Silver1 - 1629(곱셈)
// 문제링크: https://www.acmicpc.net/problem/1629

import java.util.*;

public class Main {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		long a = sc.nextLong();
		long b = sc.nextLong();
		long c = sc.nextLong();

		System.out.println(pow(a,b,c));
	}
	
	private static long pow(long a, long b, long c) {
		
		// 제곱이 1인 경우
		if(b==1) 
			return a%c;
		
		// 지수의 절반 값 구하기
		long temp = pow(a,b/2,c);
		
		// 지수가 홀수인 경우
		if(b%2==1) {
			// 먼저 나머지를 취하고 계속해서 곱함
			return temp*temp%c*a%c;
		}else {
			// 짝수인 경우
			return temp*temp%c;
		}
	}	
}

결과😎

느낀점👨‍💻

지수의 절반 값을 구하는 것은 어느 정도 생각을 했는데 지수가 홀수인 경우와 짝수인 경우에 대해서 어떻게 처리해야 될지 시간을 생각보다 많이 소모하였다.

Sinbmil의 알고리즘 문제 코드

-> https://github.com/Sinbmil/Algorithm-Study