백준 1629번 C언어 풀이

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

1629번: 곱셈

 

단순히 계속 곱했다가는 오버플로우되는 문제. 하지만 모듈러 연산을 적용한다고 해도, 일반적인 반복문으로 접근한다면 시간제한에 걸린다 O(n)이니까.

 

결국 이 문제의 핵심은

• 숫자가 오버플로우되지 않도록 모듈러연산을 계속해서 적용한다.
• O(n)으로 접근해서는 안된다.

모듈러 연산은 https://codejin.tistory.com/68를 참조하자.

 

이를 통해 다 곱하고 나누는 것이 아니라, 나머지를 계속 곱하면서 최종적인 값을 찾아야 한다.

 

그러면 오버플로우는 해결했고 이제 O(n)보다 더 빠르게 풀려면 어떻게 해야할까?

 

2^10을 계산한다고 치자. 이를 일반적으로 곱한다고 가정하면 10번의 연산을 수행할 것이다. (10번 곱하니까)

 

하지만, 2^10을 계속 분할해보자. 2^10을 2^5 * 2^5 이런식으로 말이다.

 

2^10 = 2^5 * 2^5

2^5 = 2^2 * 2^2 * 2

2^2 = 2^1 * 2^1

2^1 = 2

 

이렇게 4번의 과정을 통해 2^10을 구할 수 있게 된다. 즉, 분할정복이 이 문제의 두번째 핵심이다. 이 둘을 문제에 적용시키자.

 

#include <stdio.h>

typedef unsigned long long ull;
int mod;

int sol(int a, int b) { // return a^b mod c
    if (b == 0) return 1;
    else if (b == 1) return a;
    else {
        ull ret = sol(a, b/2);
        if (b & 1) return (a * ((ret * ret) % mod)) % mod;
        else return (ret * ret) % mod;
    }
}

int main () {
    int a, b;
    scanf("%d %d %d", &a, &b, &mod);
    printf("%d", sol(a % mod, b));
}

 

인자를 전달할 때에도 결국 우리는 나머지값이 중요하므로 a가 아닌 a % mod값을 전달하도록 한다.