[백준 / JAVA] 1629. 곱셈

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

1629번: 곱셈

 

---

💻 풀이 결과

💯 최종 코드

import java.util.Scanner;

public class Main {
	// pow 함수
	public static long pow(int a, int b, int c) {
		// base condition
		if (b == 1) {
			return a % c;
		}

		long res = pow(a, b / 2, c);
		res = res * res % c;

		// b가 짝수일 때
		if (b % 2 == 0) {
			return res;
		}
		// b가 홀수일 때
		else {
			return res * a % c;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();

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

💢 틀린 이유

• 분할 정복 기법을 쓰지 않아서 시간초과가 발생하였다.

💬 풀이 과정

• 절반으로 계속 나눠간다고 생각해야 한다.
• 짝수일 때는 그대로 res를 반환하면 되고, 홀수일 때는 a를 한번 더 곱해야 한다.

💡 깨달은 점

1. 분할 정복 기법

• 분할하여 재귀적으로 문제를 해결하는 방법이다.
• 이 문제에서 절반을 제곱하는 개념으로 생각해 보면 된다.