문제
코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,c;
ll gop(ll a, ll b){
if(b == 1) return a % c;
ll ret;
ret = gop(a, b/2);
ret = (ret * ret) % c;
if(b % 2) ret = (ret * a) % c;
return ret;
}
int main(){
cin >> a >> b >> c;
cout << gop(a,b) << '\n';
return 0;
}풀이
주어진 조건이
1. a를 b번 곱한다.
2. 모듈러 연산을 사용한다. 인데
최댓값이 21억 즉 2만 곱해도 int형은 넘어간다.
또한 21억이 3번만 곱해져도 long long 타입이 넘어가 21억을 딱 한번만 곱할 수 있다.
그렇다면 곱셈에 대한 연산을 줄어야하는데 2^8 = 2^4 2^4으로 나타낼 수 있고
2^4 = 2^2 2^2으로 나타내며 줄여갈 수 있다 이 부분을 재귀로 나타내서 곱셈의 크기를 최대한 줄인다.
코드에서 확인할 수 있듯이 자기 자신에 자기 자신을 곱하고 b에 대한 부분을 반으로 나눈다.
if문은 곱해야 할 횟수가 홀수일때를 대비한 것이다.
2^7 같은 경우는 2 ^ 3 2 ^ 3 * 2인데 이처럼 반으로 나눈 값을 서로 곱하고 a 값 자체를 다시 곱하는 형식이라 홀수일 때를 곱하면 된다.
맨 처음 if( b == 1)은 재귀함수이기에 기저사례를 추가했다. 더 곱해야할 횟수가 안남으면 return 하라는 뜻이다.
%c는 모듈러 연산의 개념을 적용시킨것이다.
결과
후기
솔직히 너무 어렵다. 재귀에 대한건 머리 속으로 잘 안돌아갈 뿐더러 막 복잡해진다. 그냥 기저 사례 하나두고 대충 돌린다는 느낌으로 하면서 익숙해지는 수 밖에 없나 싶다.
재귀, 모듈러 너무 어려웠다. 힌트 검색해서 풀었는데 진짜 이런걸 어떻게 혼자 생각해낼지 엄두가 안난다.
:)