1629 : 곱셈 - 분할 정복, 재귀함수, pow

https://www.acmicpc.net/problem/1629

1629번: 곱셈

문제요약

A를 B번 곱한 뒤 C로 나눈 나머지를 구하라

 

난이도

Silver 1

---

풀이

 

• 분할 정복 ( Divide and Conquer)
  • 작은 문제로 분할하여 해결하는 방식
• 모듈러 연산 (% 나머지 연산)에서 교환법칙이 성립한다는 것
  • (a+b)%c = a%c + b%c
  • (a*b)%c = a%c * b%c
• log n = k 
  • 2를 k번 곱하면 n이 된다.

① 제곱수를 구할 때, 지수를 작은 덩어리로 나누어 곱셈 연산 횟수를 줄이는 것

② 모듈러 연산에서 교환법칙이 성립한다는 것을 이용해 중간중간 나머지 연산을 해주어야 한다는 것이 포인트

 

---

REVIEW

 

정직하게 제곱을 구해주는 메소드인 pow,

b만큼 반복 실행하는 재귀함수를 구현하여 풀었더니 시간초과도 아니고 오답이 떴다.

 

무조건 시간초과에 걸려 오답 처리가 되려니 했는데,

틀렸습니다를 마주할 줄은 몰랐다.

 

알고 보니, overflow가 일어나 결과값이 음수가 나오는 경우가 나오기도 한다는 것.

A를 B번 모두 곱한 다음 %C를 하는 과정에서 overflow가 발생한 모양.

%C 모듈러 연산을 중간중간 수행해주면 괜찮으려나?

 

여튼, 이 문제는 분할정복의 기본적인 문제라고 한다.

이런 공식스러운 코드를 짜야 할 땐, 보고 이해하는 건 가능해도

실전에서 응용해 구현해낼 수 있을지가 미지수인데 일단은 원리 이해를 해둔다..

 

난이도 사이트 보니, 파이썬에선 pow(A,B,C) 한 줄로 해결가능한가보다.

이래서 언어를 여러 개 연마할 수 있어야 하나.

---

CODE

#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;

}

---

// 내 틀린 코드
// 중간 중간 %c를 해주도록 바꾸어줬음에도 메모리 초과 발생.

#include <bits/stdc++.h>
using namespace std;

int a,b,c;

long multiply(int n){
    if(n == 1) return a;
    return (a * multiply(n-1))%c;
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);


    cin >> a >> b >> c;

    long result = multiply(b);

    cout << result;
}