[알고리즘/수학] 나머지 분배 법칙

개요 

나머지 분배 법칙은 사칙 연산의 분배 법칙과 다릅니다.

 

나머지 분배 법칙 

아래 분배 법칙을 적용한 결과, 사칙 연산의 분배 법칙과 다르게 기존의 나머지 연산 적용이 남아있습니다.

( a + b ) % mod = ( a % mod + b % mod ) % mod

 

알고리즘 문제에서의 주의점 

간혹 알고리즘 문제에서 오버플로를 피하기 위해 편의 상 N을 나눈 값을 출력하라고 합니다. (예: 1000000) 앞서 설명했듯 나머지 분배 법칙은 사칙 연산의 분배 법칙과 다르다는 점을 명심해야 합니다. 

두 개 이상의 경우에 수를 문제 풀이 과정에서 연산해야 하는 경우 한꺼번에 묶어서 나누어 주어야 합니다. 아래 두 연산은 서로 다른 값을 도출하기 때문입니다. 알고리즘 문제에서 요구하는 사항을 정확히 인식해서 나누어 주어야 합니다.

A%mod + B%mod + C%mod

( A + B + C ) % mod

 

아래 두 코드는 서로 다른 값을 출력합니다. 문제 출력 요구사항이 첫째 줄에 정답을 1,000,000으로 나눈 나머지를 출력한다. 이므로, 모든 값을 다 더한 answer 에 1,000,000 을 나누어 주어야 합니다.

https://www.acmicpc.net/source/73882786 

long long int answer = 0;
    for(int i=0; i<2; i++){
        for(int j=0; j<3; j++){
            answer += DP[N][i][j] ;
        }
    }
    
    cout << answer % DIV;

https://www.acmicpc.net/source/73883080 

long long int answer = 0;
    for(int i=0; i<2; i++){
        for(int j=0; j<3; j++){
            answer += DP[N][i][j] % DIV;
        }
    }
    
    cout << answer;

 

참고 자료 

Khan Academy

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