[개념] 나머지 연산

코딩 테스트 문제에서 정답을 나머지 값으로 요구하는 경우가 종종 있다. 이는 자료형의 표현 범위를 넘지 않게 유도하고 나머지 연산의 원리를 알고 있는지 묻는 의도가 담겨 있다.

나머지 연산의 분배 법칙

나머지 연산은 나눗셈을 제외하고 덧셈, 뺄셈, 곱셈의 분배 법칙이 성립한다.

 

ex) A = 20, B = 6, C = 3

덧셈의 분배 법칙 성립 → (A+B) % C = (A%C + B%C) % C

(20+6) % 3 = 26 % 3 = 2 (20%3 + 6%3) % 3 = (2 + 0) % 3 = 2

뺄셈의 분배 법칙 성립 → (A-B) % C = (A%C - B%C) % C

(20-6) % 3 = 14 % 3 = 2 (20%3 - 6%3) % 3 = (2 - 0) % 3 = 2

곱셈의 분배 법칙 성립 → (A*B) % C = (A%C * B*C) % C

(20*6) % 3 = 120 % 3 = 0 (20%3 * 6%3) % 3 = (2 * 0) % 3 = 0

예제

1부터 50까지 곱한 값을 10007로 나눈 나머지를 구하시오.

 

1. 분배 법칙을 적용하지 않은 코드

import java.util.*;
import java.io.*;

class MOD {
    public static void main(String[] args) throws IOException {
        int answer = 1;
        for (int i = 2; i <= 50; i++) {
            answer *= i;
        }
        System.out.print(answer % 10007);
    }
}

int 자료형의 범위를 초과하기 때문에 원하는 결과를 얻을 수 없다. 따라서 위에서 설명한 분배 법칙을 적용시켜야 한다.

 

2. 분배 법칙을 적용한 코드

import java.util.*;
import java.io.*;

class MOD {
    public static void main(String[] args) throws IOException {
        int answer = 1;
        for (int i = 2; i <= 50; i++) {
            answer = (answer * i) % 10007;
        }
        System.out.print(answer);
    }
}

분배 법칙을 적용했기 때문에 모든 값을 곱한 뒤 마지막에 나머지 연산을 한 번만 적용하는 것과 곱셈을 수행할 때마다 나머지 연산을 적용하는 것이 동일한 결과를 도출한다.