[알고리즘/문제] 백준 1629번: 곱셈 (C++)

이번 문제도 저번 문제처럼 모듈러 연산을 활용한 문제처럼 보였다.

왜냐하면 엄청나게 큰 수를 나눈 나머지를 구해야하는 흐름이 비슷했다.

그래서 다음과 같은 코드를 짰다.

#include<iostream>
#include<string>
#include<cmath>

using namespace std;

typedef long long ll;
ll a, b, c, ret =1;


int main() {
    cin >> a >> b >> c;
    for (int i = 0; i < b; i++) ret = (ret * a ) % c;
    ret = ret%c;
    cout << ret<<'\n';

    return 0;
}

 

문제를 볼때는 항상 최대최소를 먼저 봐야한다고 한다.

그래서 문제점을 예상하긴 했는데.. 이런식으로 for문을 돌리면 b가 엄청나게 큰 수가 들어왔을때 시간이 무척 오래 걸릴것이라는 것이다.

아니랄까 제출했을때도 시간초과가 떴다.

그렇다면 재귀함수로 만들어서 b를 2로 나누면서 진행하면 시간이 확 줄어들 것이라 생각했다.

 

밑의 코드는 정답코드이다.

#include<bits/stdc++.h> 
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);
    ret = (ret * ret) % c;
    if(b % 2)ret = (ret * a)% c;
    return ret;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> a >> b >> c;
    cout << go(a, b) << "\n";
    return 0;
}

 

기저조건은 b가 1일때 a%c를 해주고,

b를 2로 나누면서 재귀호출을 해준다.

분배법칙이 적용된 (ret * ret)%c를 계속 중첩시킨다.

ret을 두 번 즉, (a%c)를 두 번 사용하니 b를 2로 나눌 수 있는 것 같다.

그리고 /2를 하면 홀수의 경우 소수점이 없어지니 홀수인 경우 한번 더 해준다.

 

재귀함수 짜는게 생각보다 어려웠다..

코드의 도움을 좀 많이 받긴했다.

이제 1주차 내용들 복습하면서 2주차로 넘어가보자

 

[강의 사이트]

https://inf.run/QKBXL

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트 강의 - 인프런