[백준(Baekjoon)][자바(java)] 1629 : 곱셈 / 분할 정복

 

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

1629번: 곱셈

 

 

< 문제 풀이 >

 

* 일반적인 재귀 호출 ( 브루트 포스 ) 식으로 풀면 시간 초과남

* 분할정복 알고리즘으로 푸는 것이 더 효율적

 

※ 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것

┌ 일반적 재귀 호출 -- 한 조각과 나머지로 쪼갬

└ 분할 정복 -- 문제를 절반씩으로 나눔

( 출처 : 알고리즘 문제 해결 전략 )

 

점화식

 

import java.util.Scanner;

public class Main {
	
	static long a, b, c;
	
	public static long pow( int k ) {
		if( k == 1 ) return a % c;
		long p = pow( k / 2 );
		long res = ( p * p ) % c;
		res = k % 2 == 1 ? ( res * a ) % c : res;
		return res;
	}

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		a = sc.nextInt();
		b = sc.nextInt();
		c = sc.nextInt();
		sc.close();

		System.out.println( pow( (int)b ) );

	}
}