[백준 1629번 C++] Silver1. 곱셈

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

핵심 아이디어 및 정답 코드

범위를 쉽게 벗어날 수 있으므로, 유의
 -> 모듈러 성질 이용 : (A * B) % C = (A % C) * (B % C)

 

1) O(N) 계산 : 시간 초과

- O(log N) 이하의 시간 복잡도로 풀어야 함

 -> 지수 법칙 이용 : A^(N+M) = A^N * A^M

 

2) dp로 저장 : 메모리 초과

- B / 2 만큼의 연산을 dp에 미리 담아두어 dp[B/2] * dp[B/2] * dp[B%(B/2)]로 계산하려고 시도

 -> 재귀를 이용하여 연산량을 줄임

 

3) 재귀를 사용 : 통과

- 재귀를 이용해 현재 넘어온 B 값이 짝수, 홀수인지에 따라 연산

 -> 짝수 : A^B % C / 홀수 : A^(B + 1) % C

 

정답 코드

#include <iostream>
using namespace std;

int A, C;
long long GetAnswer(int B)
{
    if (B == 1)
        return A % C;

    long long answer = GetAnswer(B / 2) % C;
    answer = answer * answer % C;
    return (B % 2 == 0) ? answer : answer * A % C;
}

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

    int B;
    cin >> A >> B >> C;
    cout << GetAnswer(B);

    return 0;
}