(22.06.17) (Baekjoon) 1629. 곱셈

 

1629번: 곱셈

시간 제한 : 0.5초(추가 시간 없음)

메모리 제한 : 128MB

정답 비율 : 26.116%(06.17 기준)

 

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

예제 입력 1 복사

10 11 12

예제 출력 1 복사

4

 

이전에 올렸던 행렬 제곱과 같은 방식으로 풀 수 있는 문제다.

이 문제를 풀고 행렬 제곱 문제로 가면 더 쉽게 풀 수 있을 것 같다.

 

(a의 b승) % c인 문제.

 

풀이의 논리를 설명하자면

a,b,c가 주어졌을 때,

- b가 짝수이면

현재 a값을 제곱하고, b/2를 한다.

- b가 홀수이면

현재 a값에 처음의 a값을 곱해주고, b-1을 해준다.

 

두 경우 모두 c로 나머지 연산을 진행하는 것을 잊지 말자.

그렇게 분할을 이어가다가 b가 1이 되면 더이상 제곱을 할 필요가 없으므로 최종 a%c를 반환하면 된다.

 

import java.util.*;
public class Main {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
Scanner s = new Scanner(System.in);
long a = s.nextLong();
long b = s.nextLong();
long c = s.nextLong();
long d =  (long)Math.pow(a, b);

System.out.println(cal(a,b,c));
	}
	
	private static long cal(long a,long b,long c)
	{
		if(b == 0)
			return 1; // 0승이면 무조건 1이 나옴
		if(b ==1)
			return a%c;
		
		if(b%2 == 0)
		{
			long d = cal(a,b/2,c);
			return d*d %c;
		}
		else
		{
			long d = cal(a,b-1,c);
		return (a*d) %c;
		}
	}
}

 

화요일에 올렸어야 하는 걸 이제야 올리게 되었다. 여러모로 좀 게을렀던 것 같다.

분할정복이 낯설어서 정답률이 낮을 뿐, 크게 어려운 문제는 아니니 풀어보면 좋을 것 같다.