[백준]BOJ_실버 1 _1629 곱셈_C++ 분할정복/재귀

1629번: 곱셈 (acmicpc.net)

1629번: 곱셈

#include <iostream>
using namespace std;

long long f(long long A, long long B, long long C){
	if(B==0){
return 1;}
long long X = f(A ,B/2, C);
if(B%2==0)
{
return X*X %C;
}

return X%C *X%C*A%C;}// <=주의!! 각 문자별로 %C를 바로바로 안해주면 오버플로우 발생

int main()
{
   ios_base::sync_with_stdio(false); 
	cin.tie(nullptr); 
	cout.tie(nullptr);
   long long A,B,C=0;
	cin >> A>>B>>C;
	cout << f(A,B,C);
	
    return 0;
}

<코드해석>

SCCC 스터디에서 풀었는데 도움 받으면서 풀긴 했지만 순식간에 풀어서 너무 뿌듯했다!!

(재귀함수 f)

1. int형 보다 큰 비트수를 넣어줘야 해서 long long형을 이용해줘한다.

-> 왜냐면 A를 B번 곱한 수를 구하는 것이기 때문에 매우 커질것임을 예측할 수 있다.

2. B가 0이면 A^0=1 이라서 1을 리턴해준다.

3. 그다음 long long형 X를 통해 재귀함수를 이용해준다,

4. f(A, B/2, C)의 값을 받았을 테니 B%2==0(B가 짝수일 경우)일 때 return X*X => A를 B번 곱함 => A의 B승 

X^2=A^B/2^2=A^B여기에 %C를 해줘서 제시된 조건을 만족하도록 해준다.

5.홀수일 경우에는 A를 한번 더 곱해줌으로써 B%2==1이니깐 A를 넣어줌으로써 날아가는 나머지인 1을 채워준다.

6. else if를 쓸 필요가 없는게 어차피 재귀로써 이미 해당영역이면 return해버린다. 

7. 주석 처리 해놓은 것 처럼 %C로 바로바로 나눠주지 않으면 오버플로우 오류가 뜬다.

 

(메인 함수)

1.A,B,C를 받아서 

2. f(A,B,C)를 출력해준다.

 

분할정복을 이용한 문제 ! 

이런 식으로 분할해서 풀 수 있다는 것을 알게 돼서 신기했다.