배푸니까

[백준 / JAVA] 1629. 곱셈 본문

백준

[백준 / JAVA] 1629. 곱셈

baefrica 2023. 10. 22. 00:23
반응형

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

 

1629번: 곱셈

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

www.acmicpc.net

 


💻 풀이 결과

💯 최종 코드

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. 분할 정복 기법

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

'백준' 카테고리의 다른 글

[백준 / JAVA] 15649. N과 M (1)  (1) 2023.10.22
[백준 / JAVA] 2146. 다리 만들기  (0) 2023.10.16
[백준 / JAVA] 13549. 숨바꼭질3  (0) 2023.09.03
[백준 / JAVA] 2573. 빙산  (0) 2023.08.31
[백준 / JAVA] 2206. 벽 부수고 이동하기  (0) 2023.08.30