[문제풀이] BOJ 10430. 나머지

Baekjoon Online Judge 알고리즘 문제풀이(Java)

BOJ 10430. 나머지
(출처 : 문제의 저작권은 BOJ에 있습니다. )

---

🗒️ 문제

<문제>
(A+B)%C는 ((A%C) + (B%C))%C 와 같을까?

(A×B)%C는 ((A%C) × (B%C))%C 와 같을까?

세 수 A, B, C가 주어졌을 때, 위의 네 가지 값을 구하는 프로그램을 작성하시오.

<입력>
첫째 줄에 A, B, C가 순서대로 주어진다. (2 ≤ A, B, C ≤ 10000)

<출력>
첫째 줄에 (A+B)%C, 
둘째 줄에 ((A%C) + (B%C))%C, 
셋째 줄에 (A×B)%C, 넷째 줄에 ((A%C) × (B%C))%C를 출력한다.

테스트 케이스는 BOJ의 해당 문제를 확인 바랍니다.

---

🎈 나의 풀이

package AlgorithmBase1;

import java.io.IOException;
import java.util.Scanner;

public class P10430 {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int A = sc.nextInt();
        int B = sc.nextInt();
        int C = sc.nextInt();

        System.out.println((A+B)%C);
        System.out.println(((A%C) + (B%C))%C);
        System.out.println((A*B)%C);
        System.out.println(((A%C) * (B%C))%C);
    }
}

 

---

💬 짚어가기

해당 문제는 모듈러 연산의 기본 성질을 확인할 수 있는 문제이다.
모듈러 연산에 대해 살펴보자.

모듈러 연산(Modular arithmetic)

모듈러 연산은 어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산이다. 두 정수 A, B에 대해서
A를 B로 나누어 나머지가 C가 나왔다면 A mod B = C 또는 A % B = C라고 표현할 수 있다.

▶︎ 모듈러 합동(Modular congruent)

두 수 $a$, $b$가 mod $n$의 결과가 같다면, _모듈러 합동관계(congruent modulo n)_라고 한다.

• $a$ $mod$ $n = b$ $mod$ $n$
• $a \equiv b$ $mod$ $n$

합동 관계를 쉽게 알아내는 방법
mod $n$에 대해, $a-b = kn$ 일때 $a$와 $b$는 합동(Congruent)관계이다. (k는 정수)
예) 73과 4가 mod 23에 대해 합동관계이면, $73-4 = 69 = (23 * 3)$을 만족한다.

 

▶︎ 모듈러 연산의 특징

모듈러 연산은 덧셈, 뺄셈, 곱셈 연산에 대한 아래와 같은 특징을 갖는다.

• $(a$ $mod$ $n + b$ $mod$ $n)$ $mod$ $n = (a + b)$ $mod$ $n$
• $(a$ $mod$ $n - b$ $mod$ $n)$ $mod$ $n = (a - b)$ $mod$ $n$
• $(a$ $mod$ $n * b$ $mod$ $n)$ $mod$ $n = (a * b)$ $mod$ $n$

곱셈 연산의 특징을 이용하여 거듭제곱에 대한 나머지 연산에도 활용할 수 있다.

 

▶︎ 모듈러 나눗셈(Modular Division)

모듈러 연산은 일반적으로 정수에 대한 연산이다.
그렇다면 정수가 아닌 값에 대한 모듈러 연산은 어떻게 수행할 수 있을까?

$5/3$ $mod$ $11$와 같은 식의 모듈러 연산을 수행한다고 가정하자.

이러한 분수 형태의 모듈러 연산을 위해선 역원을 구하여 해결할 수 있다.
(역원이란 두 원소를 연산한 결과가 항등원일 때, 한 편에 대하여 다른 편을 이르는 말이다.)

분모인 $3$의 역원 $t$ 를 구해보자.

$3 * t$ $mod$ $11 = 1$
$3 * 4$ $mod$ $11 = 1$

이를 만족하는 $t$의 값은 $4$이다. 따라서 $3$의 역원 $4$를 구할 수 있다.
이제 기존 식을 역원을 이용하여 변형하면 아래와 같다.

$5/3$ $mod$ $11 = 5 * 4$ $mod$ $11 = 9$의 결과를 얻을 수 있다.

 

👀 모듈러 나눗셈 짚어아기

사실 $5/3$ $mod$ $11$ 과 같은 식을 보았을 때, $5/3$의 근사값이 나와야 하지 않나 하는 의문이 들었다.
$5/3$은 약 1.6666666667이고, 계산기에 $(5/3)$ % $11$을 해보면 동일한 결과가 나온다.

원인은 _계산 방식과 목적성_에 따른 결과 차이이다. 단순 계산기에서의 나눗셈은 실수 연산이므로 소수점
이하 결과를 포함한다. 따라서 계산기에서는 소수점 이하가 포함된 결과가 나오게 된다.

모듈로 연산은 정수의 주기성을 나타내거나 암호학 등에 활용된다.
모듈러와 계산기에서의 나눗셈은 다른 목적과 연산 방식을 가지고 있기 때문에 결과가 서로 다를 수 있다.