[BAEKJOON] 백준 15818: 오버플로우와 모듈러 (C#)

문제 링크

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

 

 

문제

정수 오버플로우(Integer Overflow)란 정수형 변수가 연산 중 표현 범위를 넘어 의도와는 다른 값이 저장되는 현상을 말한다. C/C++, Java와 같이 변수의 타입과 함께 그 크기가 미리 정해지는 언어에서 종종 발생한다.

변수의 타입에 대해 공부했다면 231-1, 2,147,483,647과 같은 수가 익숙할 텐데 이는 일반적인 4byte Integer 변수로 표현할 수 있는 양의 정수의 최댓값이다. 만약 4byte Integer 변수 1,000,000과 1,000,000을 곱하면 어떻게 될까? 결과는 컴파일러마다 다를 수 있지만, 우리가 원하는 값인 1,000,000,000,000이 나오지는 않을 것이다. 이미 연산과정에서 표현할 수 있는 범위를 벗어난 이 값은 4byte Integer가 표현 가능한 다른 값으로 변형되어 있을 것이다.

그렇다면 어떻게 할 수 있을까? 첫 번째는 보다 큰 범위의 정수 변수를 사용하는 것이다. 예를 들어 int가 아닌 C/C++에서의 long long, Java에서의 long과 같은 타입을 사용하면 우리는 -263 ~ 263-1 까지의 정수를 표현할 수 있다. 또한 놀랍게도 Python과 같이 타입에 따른 메모리 제한이 없어 사용자가 오버플로우에 대한 처리를 고려하지 않아도 되는 언어들도 있다.

이 문제에서 우리는 N개의 정수를 곱할 것이다. 하지만 정수의 곱이란 너무나도 빠르게 증가하기 때문에 그 결과가 정수변수로 표현할 수 있는 범위를 넘어갈 수도 있다. 그러니 우리는 (A × B) % M = ((A % M) × (B % M)) % M 과 같은 공식에 착안하여 N개의 정수를 곱한 결과값을 M으로 나눈 나머지를 비교하도록 하자.

N개의 정수와 M이 주어질 때, 모든 정수의 곱을 M으로 나눈 나머지를 계산하는 프로그램을 작성하시오.

 

 

입력

첫 줄에 연산될 정수의 개수 N(1 ≤ N ≤ 100)과 M(1 ≤ M ≤ 2,147,483,647)이 주어진다. 두 번째 줄에는 N개의 정수 ai (1 ≤ ai ≤ 2,147,483,647)가 한 줄로 주어진다. 

 

 

출력

한 줄에 N개의 정수의 곱을 M으로 나눈 나머지를 출력한다.

 

 

 

통과한 답안

namespace _15818
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string[] inputs = Console.ReadLine().Split(' ');
            int N = int.Parse(inputs[0]);
            int M = int.Parse(inputs[1]);
            long[] arr = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
            long answer = 1;

            for (int i = 0; i < arr.Length; i++)
            {
                answer *= arr[i] % M;
                answer %= M;
            }

            Console.WriteLine(answer);
        }
    }
}

 

int의 범위와 오버플로우를 생각해보게 하는 문제로

이 문제에서 가장 중요한 공식은 아래의 곱셈 공식이다.

(A * B) % M = ((A % M) * (B % M)) % M

이다.

 

문제를 해결하는 방법은 주어진 입력값들을 받아온 후에

answer를 1로 시작하여, 모든 값을 M으로 나눈 값을 곱해주고,

answer를 M으로 나눠주는 것으로 해결할 수 있다.

 

문제 자체는 주어진 공식을 구현하는 간단한 문제였지만,

문제를 풀면서 정수의 범위를 테스트해볼 수 있는 문제였다.