재귀 함수를 구현할 때, base condition(탈출 조건)을 2*2 즉 한 변의 길이가 2일 때로 설정하면 된다.
그리고 순회하면서 0부터 쭉 순회 순서를 카운트 해줘야하기 때문에 전역 변수로 cnt를 두었다.
그림을 보면 n = 2일 때는 n = 1일 때의 상황이 네 번 반복된다.
또한 n = 3일 때는, n = 2일 때의 상황이 네 번 반복된다는 것을 알 수 있다.
따라서 base condition이 아닌 n을 처리하기 위해서는 4번의 n - 1을 처리하는 과정이 필요하다는 것을 알 수 있다.
2의 n승 형태로 인자가 들어가기 때문에 1<<n을 사용했다.
#include<iostream>
using namespace std;
int cnt = 0;
int n, r, c;
void func(int len, int row, int col) {
//base condition: n = 2일 때
if (len == 2) {
if (row == r && col == c) {
cout << cnt << '\n';
return;
}
else
cnt++;
if (row == r && col + 1 == c)
{
cout << cnt << '\n';
return;
}
else
cnt++;
if (row + 1 == r && col == c)
{
cout << cnt << '\n';
return;
}
else
cnt++;
if (row + 1== r && col + 1 == c)
{
cout << cnt << '\n';
return;
}
else
cnt++;
return;
}
func(len / 2, row, col);
func(len / 2, row, col + len / 2);
func(len / 2, row + len / 2, col);
func(len / 2, row + len / 2, col + len / 2);
}
int main(void) {
cin >> n >> r >> c;
func(1 << n, 0, 0);
return 0;
}
수의 범위가 20억까지 가능하기 때문에 long long 타입을 활용한 것 이외에 재귀를 진행할 때도 아이디어가 하나 필요했다.
B가 홀수냐 짝수냐에 따라서 경우를 나눠줬다.
재귀의 base condition은 B가 0일 때 1을 반환하는 것이 된다.
또한 overflow를 방지하기 위해 계산하는 중간중간에 modular 연산을 수행해줄 필요가 있다.
XYmodM = (XmodM * YmodM) mod M 인 것을 이용하면 되겠다.
지수가 홀수인 경우, 계산 이후에 a를 한 번 더 곱해줘야 하고, 이 과정에서 modular 연산을 한번 더 수행해줘야 한다.
#include<iostream>
using namespace std;
typedef long long ll;
ll POW(ll a, ll b, ll m){
if(b == 0) return 1;
ll val = POW(a, b/2, m);
val = val * val % m;
//b가 짝수, 홀수인 경우 나눠서 처리
if(b % 2 == 0) return val;
else
return (val * a) % m;
}
int main(void){
int a, b, m;
cin >> a >> b >> m;
cout << POW(a, b, m);
return 0;
}