문제

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

아이디어

1. 단순하게 Python으로 A의 B승을 구하여 C로 나눈 나머지를 출력
   • 시간초과
2. 반복문으로 A에 B를 곱해주며 매번 C를 나눠준다
   • 시간초과
3. 나머지가 생기는 규칙적인 패턴이 있으므로 패턴을 찾아서 접근
   • 시간초과

아무리 생각해도 시간초과를 발생시키지 않고 풀지 못하겠어서 검색하였다.

참고

• https://velog.io/@litien/BOJ-1629-%EA%B3%B1%EC%85%88

코드

#include <iostream>

long long getExponent(int a, int b, int c)
{
	if (b == 0) {
		return 1;
	}

	return (b % 2 == 1) ? (getExponent(a, b/2, c) * getExponent(a, b/2, c) % c * a % c) : (getExponent(a, b/2, c) * getExponent(a, b/2, c) % c);
}


int main(void)
{
	int a, b, c;

	scanf("%d %d %d", &a, &b, &c);
	
	printf("%lld\n", getExponent(a, b, c));

	return 0;
}

리뷰

• 전형적인 재귀함수를 사용한 분할정복 문제
• 큰 수에 접근하는 문제면 분할정복을 사용해야 하지만 매번 까먹는다.