백준 10430번 : 나머지 (모듈러 연산)

모듈러연산

※ 문제 풀기 전 알면 좋은 지식! - 모듈러 연산 (Modular Arithmetic)

모듈러 연산은 양수를 나눌 때 사용하는 특별한 방법이다.

주로 순환성을 모델링하는데 유용한데, 대표적인 순환성 계산이라고 한다면 시간이나 요일 등이 있을 것이다.

 

만약 "n일 후"의 요일을 구한다고 생각해보자. 이 때, 1은 월요일, 2는 화요일 ... 7은 일요일을 나타낸다.

 

그렇다면 "O요일의 n일 후는 무슨 요일"일까?

계산식은 아래와 같다.

A mod B = R

10 mod 3 = 1

이는 나머지 값을 나타내는 것으로 mod 연산자를 사용하게 된다.

 

그래서 월요일의 8일 후라고 하면 (1 + 8) % 7 = 2가 되어서 2는 화요일을 의미한다.

금요일의 15일 후는 (5 + 15) % 7 = 6이 되고, 6은 토요일을 의미한다.

마지막으로 일요일의 28일 후라고 한다면 (7 + 28) % 7 = 0이 되는데 이는 일요일을 의미한다.

 

만약 C++과 Javascript를 이용해서 이를 계산하면 아래와 같다.

#include <iostream>
using namespace std;

int main() {
    int a = -7;
    int b = 3;

    int result = a % b;  // -7을 3으로 나눈 나머지 계산

    cout << result << endl;  // 2

    return 0;
}

분명 -7 % 3을 하면 -1이 나오는데 위 결과는 2가 나오는 것을 알 수 있다.

 

그 이유는 % 연산자는 음수의 경우 결과를 양수로 조정하기 때문이다.

나머지는 "0보다 크거나 같고, 나누는 값보다 작다" 라고 한다.

그래서 음수가 나오는 경우 3을 더한 결과 값인 2를 출력하게 되는 것이다.

만약 음수를 원한다면 계산 후에 수동으로 음수로 변환해야한다.

 

Javascript의 경우에는 음수 그대로를 노출해준다.

function mod(n, m) {
  return (n % m);
}

그렇기 때문에 위 코드를 아래와 같이 수정해야한다.

function mod(n, m) {
  return ((n % m) + m) % m;
}

 

모듈러 연산은 주기적인 패턴을 가지는 데이터를 다룰 때 유용하다.

 

---

문제

---

#include <iostream>
using namespace std;

int main() {
    int A, B, C;

    cin >> A >> B >> C;

    cout << (A + B) % C << '\n';
    cout << ((A % C) + (B % C)) % C << '\n';
    cout << (A * B) % C << '\n';
    cout << ((A % C) * (B % C)) % C << '\n';

    return 0;
}