[백준][C#] 1629 곱셈 - 실버1

문제 풀기

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

1629번: 곱셈

 

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

 

 

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

 

 

 

2,147,483,647를 세 번 곱하는 순간 long 안에 담을 수 없기 때문에

모듈러 연산을 필수로 하는 문제다.

 

사실 실버1 문제 치고는 쉬워 보이나, 제한 시간이 0.5초인 것을 볼 수 있다.

그저 수를 하나씩 곱해주는 방식은 O(n)이라는 시간이 걸리기 때문에

2,147,483,647번 곱해야 하는 상황이 오면 제법 끔찍할 것이다.

(동시에 모듈러 연산도 같이 해줘야하니...)

 

그래서 알고리즘 분류를 확인해보면

분할 정복을 이용한 거듭제곱이라는 알고리즘을 볼 수 있다.

 

이것이 무엇이고 C#으로 어떻게 구현을 하였는지,

코드를 확인해보도록 하자.

// a, n, c는 지문의 A, B, C이다.
private static long Pow(long a, long n, long c)
{
	// result에 a를 곱할 것이다.
    long result = 1;
    while(n > 0)
    {
    	// 비트 연산
        // 1을 이진수로 쓰면 1
        // 1과 비트가 겹친단 뜻이기 때문에, 홀수라는 뜻 (n % 2 != 0)
        if((n & 1) == 1)
        	// 홀수일 때는 a를 한 번 곱해준다.
            // 곱셈이 한 번 들어갈 때마다 모듈러 연산을 해주자.
        	result = (result * a) % c;
		
        // 매 루프마다 a를 제곱해준다.
        // 곱셈이 한 번 들어갈 때마다 모듈러 연산을 해주자.
        a =( a * a )% c;
		
        // 한 번 제곱을 해주었기 때문에 비트 연산
        // 오른쪽으로 밀어준다.
        n = n >> 1;

    }

    return result;
}

처음 보면 while 문 안의 내용이 이해가 되지 않을 것이다.

나도 그랬기 때문이다.

 

분할 정복을 이용한 거듭제곱의 원리를 알아보겠다.

 

예제처럼 3^11을 계산한다고 생각해보자.

3^11의 지수를 2와 1로만 이루어지도록 쪼개보자.

3^11 = 3^10 x 3^1 = (3^5)^2 x 3^1 = (3^4 x 3^1)^2 x 3^1 = ((3^2)^2) x 3^1)^2 x 3^1

 

((3^2)^2) x 3^1)^2 x 3^1

 

이제 슬슬 로직이 이해가 될 것이다.

이제 뒤에서부터 계산을 해본다.

 

((3^2)^2) x 3^1)^2 x 3^1

11은 홀수니까, 짝수로 만들기 위해 1을 빼주다보니 x 3의 1제곱이 남게 된다.

result = (result * a) % c;

 

((3^2)^2) x 3^1)^2

제곱을 해줄 차례다.

a =( a * a )% c;

 

그래 이제 저 두 연산은 알겠다.

그런데

n = n >> 1;

는 무슨 뜻일까?

a에 제곱을 해주었으면 n도 2로 나누어줘야 하니까.

11을 2로 나누어 준다는 뜻이다. (비트 하나당 x2만큼의 가치가 있기 때문에.)

 

((3^2)^2) x 3^1

result = (result * a) % c;

 

(3^2)^2

a =( a * a )% c;

 

3^2

a =( a * a )% c;

 

 

빠른 계산을 위해 비트 연산을 사용해서 어려워보였을 뿐.

원리는 간단하다.

 

 

전체 코드

 

internal class Program
    {
        static void Main(string[] args)
        {
            using var reader = new System.IO.StreamReader(Console.OpenStandardInput());
            using var print = new System.IO.StreamWriter(Console.OpenStandardOutput());

            string[] inputs = reader.ReadLine().Split();

            long A = long.Parse(inputs[0]);
            long B = long.Parse(inputs[1]);
            long C = long.Parse(inputs[2]);

            print.WriteLine(Pow(A, B, C));
        }

        private static long Pow(long a, long n, long c)
        {
            long result = 1;
            while(n > 0)
            {
                if((n & 1) == 1)
                    result = (result * a) % c;

                a =( a * a )% c;

                n = n >> 1;

            }

            return result;
        }
    }