백준 1629 곱셈(모듈러, 재귀)

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;

ll a,b,c;

ll go(ll a, ll b) {
    if (b == 1) return a % c;
    ll ret = go(a, b / 2); // 2의 5승을 2의2승 * 2의 2승 * 2로 바꾸는 연산
    ret = (ret * ret) % c; // 곱해준 걸 모듈러 연산
    // 홀수인 경우에는 a를 한번 더 곱해주는 연산
    if(b%2 != 0)ret = (ret * a) % c;
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> a >> b >> c;
    cout << go(a,b) << '\n';
    return 0;
}

 

• 풀이

 

a * b % c를 구하는 문제, a와 b가 ㅈㄴ 크다

모듈러 연산, 재귀 연산을 둘다 사용해서 푸는 문제

 

모듈러 연산

(a+b)%c = a%c + b%c

(a*b) %c = a%c * b %c

 

재귀

2^4 = 2^2 * 2^2

2^8 = 2^4 * 2^4 형태로 표현 가능하다

재귀로 반으로 줄이고, 모듈러 나머지 연산을 적용해서 크기를 줄이는 방식으로 long long 범위안에서 log2n으로 답을 구할 수 있었다

 

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;

ll a,b,c;

ll go(ll a, ll b) {
    if (b == 1) return a % c;
    ll ret = go(a, b / 2); // 2의 5승을 2의2승 * 2의 2승 * 2로 바꾸는 연산
    ret = (ret * ret) % c; // 곱해준 걸 모듈러 연산
    // 홀수인 경우에는 a를 한번 더 곱해주는 연산
    if(b%2 != 0)ret = (ret * a) % c;
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> a >> b >> c;
    cout << go(a,b) << '\n';
    return 0;
}

 

재귀.. 라는걸 문제를 보면 딱 바로 떠올렸어야 됬는데 그 부분이 잘 되지 않았다..

다음부터는 비슷한 유형의 문제가 나오면 바로 적용 가능하게 노력하자