첫번째 풀이
: 당연히 시간 초과 발생함.
-> 왜냐하면, a,b,c 무 2147483647 이하의 자연수이다.
그러면 2147483647의 2147483647 승 처리하면... 시간 초과.
long long a, b, c;
int main()
{
cin >> a >> b >> c;
for (long long i = 0; i < b; ++i)
{
a *= a;
a %= c;
}
cout << a;
}-
이러한 생각을 해볼 수 있다.
: 10의 10승의 경우, 시간복잡도는 10의 10승이다. -
그런데 , 10의 10승은 10의 5승 * 10의 5승이다.
-> 이렇게 되면 시간 복잡도는 10의 5승 밖에 안된다. (자기 자신을 곱하면 된다. -
그러면 10의 5승을 더 줄여보려고 한다면 ? 10의 2승 10의 2승 (곱하기) 10 이다.
: 그러면 시간복잡도는 10의 2승이 된다. -
결론
: 짝수일 경우, 제곱근의 시간복잡도로 처리가 가능하다.
- 위의 그림을 참고하면 트리 형태로 나타낼수 있고, 이것은 재귀로 처리가 가능하다.즉 위의 문제는 분할 정복을 해야겠다는 생각을 해야 한다.
두번째 풀이.
- 틀렸다는 오류 발생한다.
: 위의 생각한것들 중에서 10의 4승의 경우,
10의 2승을 자기 자신을 곱하기 하면된다.
그런데 아래의 코드는 자기 자신을 곱하는 것이 아닌, 재귀를 2개 하고 있는 형태의 코드이다. 호출 스택이 당연히 증가해서 메모리 크기가 커질 수 있다.
-> 다른 방법을 고려하자. 내가 생각한 거, 자기 자신을 곱하기 방식으로 접근하면 된다.
#include <iostream>
#include <typeinfo>
#include <stack>
#include <string>
using namespace std;
long long a, b, c;
long long func(long long target, long long cnt)
{
if (cnt == 1)
return target;
int ccnt = cnt % 2;
if (ccnt == 1)
{
return func(target, cnt / 2)
* func(target, cnt / 2) * target % c;
}
else
{
return func(target, cnt / 2) * func(target , cnt / 2)
% c;
}
}
int main()
{
cin >> a >> b >> c;
// 10의 10승일 경우
// 10의 5승 * 10의 5승이 좋고
// 10의 2승 * 10의 2승 * 10 // 10의 2승 * 10의 2승 * 10
// 10 * 10 / 10 * 10 / * 10 ///
cout << func(a, b);
}세번째 풀이 .
: 자기 자신을 구해서 먼저 처리 한후, 어떻게 할까? 를 생각하자.
- 생각할 부분. 재귀의 경우, 가장 작은 거부터 처리한 다음에 다시 복귀한다는 것을 생각하면 문제를 풀기에 쉽다.
#include <iostream>
#include <typeinfo>
#include <stack>
#include <string>
using namespace std;
long long a, b, c;
long long func(long long target, long long cnt)
{
if (cnt == 1)
return target % c;
int ccnt = cnt % 2;
long long temp = func(target, cnt / 2);
temp = temp * temp % c;
if (ccnt == 1)
{
return temp * target % c;
//return func(target, cnt / 2)
// * func(target, cnt / 2) * target % c;
}
else
{
return temp % c;
//return func(target, cnt / 2) * func(target , cnt / 2)
// % c;
}
}
int main()
{
cin >> a >> b >> c;
cout << func(a, b);
}생각해보기
10의 5승 이라고 한다면,
func(10 , 5) 이고,
func(10, 5) 진입. 함수 내부에서 temp = func(10 , 2);
temp = temp % c; 이 상태를 유지하고 있는데.
if (ccnt == 1)
{
return temp * target % c;
}
else
{
return temp % c;
} // 여기까지인데. 재귀가 있다...
func(10, 2);를 먼저 진행한다.
func(10 , 2); 가 진입하면 이렇게 된다.
ong long func(long long target, long long cnt)
{
if (cnt == 1)
return target % c;
int ccnt = cnt % 2;
long long temp = func(10, 1); //=> 또 재귀 진입.
temp = temp temp % c;
if (ccnt == 1)
{
return temp target % c;
}
else
{
return temp % c;
}
}
결국 func(10, 1); 의 경우, 출력은 10 % 4가 된다.
일단 간단하게 확인하기 위해서 return target; 이라고 생각하면
func(10 , 1); 은 10이 나온다.
다시 func(10, 2); 로 향하자.
ong long func(long long target, long long cnt = 1)
{
if (cnt == 1)
return target % c;
int ccnt = cnt % 2;
long long temp = 10
temp = 10 10 (% c(생략) ) ;
if (ccnt == 1)
{
return 10 10 // % c;(생략)
}
else
{
return temp % c;
}
}
-> func(10, 2) 의 결과는 100 반환.
다시 맨위로 오자.
10의 5승 이라고 한다면,
맨 처음 호출한 func으로 진입하자.
func(10, 2) 진입. 함수 내부에서 temp = 100; 라는 결과를 얻었다.
temp = 100 100 ;
if (ccnt == 1)
{
return 10000 target (10) % c;
}
else
{
return temp % c;
}
-> 최종 적으로 10000 * 10을 구할 수 있다....
