C# - 모듈러 연산(나머지 분배 법칙)

백준에서 DP관련 문제를 풀때 출력 부분에 큰 수로 나눈 나머지를 구하라는 부분이 계속 있어서 이부분이 왜 필요한지 자세히 알고 싶어졌다.

---

 

모듈러(Modulo)

나눗셈의 나머지를 계산하는 연산이다. 일반적으로 mod 혹은 %기호료 표시된다. 

a mod b = r

a = 나눠지는수, b = 나누는 수, r 나머지

---

모듈러 연산과 분배법칙

어떤 수 m으로 나누었을 때 나머지는 덧셈에 대해 분배된다.

( a + b ) mod m = (( a mod m )+( b mod m )) mod m

예시

( 7 + 5 ) mod 3=(( 7 mod 3 )+( 5 mod 3 )) mod 3
12 mod 3 = ( 1 + 2 ) mod 3
0 = 3 mod 3

---

DP에서 왜 모듈러 연산을 사용할까?

중간에 발생하는 값들이 매우 커져 정수의 표현 범위를 초과할 때 컴퓨터에서 처리할 수 있는 유효한 값으로 결과를 제한하기 위해서이다. 또한 나머지를 사용함으로써 overflow를 방지하고 계산을 효율적으로 처리할 수 있게 된다.

예시

 

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력