BOJ 15818 오버플로우와 모듈러

By kuper0201

Published in 알고리즘

2023-05-25

1 min read

문제

입력

풀이

문제

BOJ 15818 오버플로우와 모듈러 바로 가기

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

변수의 타입에 대해 공부했다면 $2^{31}-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과 같은 타입을 사용하면 우리는 $-2^{63} \sim 2^{63}-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)가 한 줄로 주어진다.

풀이

해당 문제는 문제점과 해결 방안을 모두 문제에서 제시해 주고 있다.

따라서 제시된 대로 구현만 하면 해당 문제를 해결 할 수 있다.

문제에서 제시한 문제점과 해결 방안을 다시 정리하자면 아래와 같다.

입력 가능한 정수의 크기 제한으로 인해 곱셈 연산을 진행하다 보면 오버플로우가 발생하여 정상적인 계산이 불가능하다.

따라서 문제에서 제시한 $(A × B) \% M = ((A \% M) × (B \% M)) \% M$ 공식을 이용하여 각 연산의 결과값이 M이상이 되지 않도록 하여 문제를 해결하여야 한다.

코드 보기(Java)

import java.io.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // N, M 입력
        String[] s = br.readLine().split(" ");
        int N = Integer.parseInt(s[0]);
        int M = Integer.parseInt(s[1]);

        // N개의 정수 입력
        s = br.readLine().split(" ");

        long res = 1;
        for(int i = 0; i < N; i++) { // 곱셈 계산
            res *= Integer.parseInt(s[i]);
            res %= M;
        }

        System.out.println(res % M);
    }
}

코드 보기(C++)

#include <iostream>

#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
#define endl '\n'

using namespace std;

int main() {
    fastio;
    
    // N, M 입력
    int N, M, t;
    cin >> N >> M;
    
    long res = 1;
    for(int i = 0; i < N; i++) { // 곱셈 계산
        cin >> t; // 정수 입력
        res *= t;
        res %= M;
    }
    
    cout << res % M << endl;
    
    return 0;
}

코드 보기(Kotlin)

fun main(args: Array<String>) = with(System.`in`.bufferedReader()) {
    // N, M 입력
    var s = readLine().split(" ")
    var N = s[0].toInt()
    var M = s[1].toInt()

    // N개의 정수 입력
    s = readLine().split(" ")

    var res = 1
    for(i in 0 until N) { // 곱셈 계산
        res *= Integer.parseInt(s[i])
        res %= M
    }
    
    println(res % M)
}

코드 보기(Python)

from sys import stdin

def main():
    # N, M 입력
    s = stdin.readline().split(' ')
    N = int(s[0])
    M = int(s[1])

    # N개의 정수 입력
    s = stdin.readline().split(' ')

    res = 1
    for i in range(0, N): # 곱셈 계산
        res *= int(s[i])
        res %= M

    print(res % M)

if __name__ == "__main__":
    main()

코드 보기(Swift)

import Foundation

func main() {
    // N, M 입력
    var s = readLine()!.split(separator: " ")
    var N = Int(s[0])!
    var M = Int(s[1])!

    // N개의 정수 입력
    s = readLine()!.split(separator: " ")

    var res = 1
    for i in 0..<N { // 곱셈 계산
        res *= Int(s[i])!
        res %= M
    }

    print(res % M)
}

main()