분배법칙

[dp] 모듈러 분배법칙

코딩테스트를 풀다보면 결과 값이 매우 큰 경우 값의 나머지를 구하라는 문제가 자주 출제된다. 단순히 결과 값에 모듈러 연산을 수행하면 이미 결과값이 너무 커져서 오버플로우가 발생하거나 연산에 시간이 오래 걸리는 경우바 발생한다. 따라서 이럴때 연산 과정 중간에 모듈러 연산을 적용해야 한다. 연산 과정중에 모듈러 연산을 적용하기 위해서는 모듈러 연산의 분배법칙에 대해 알아야한다. 각 피연산자에 모듈러 연산을 취하고 계산 결과에 다시한번 모듈러 연산을 취하면 된다. ( dp[i] + dp[j] ) % C = ( dp[i]%C + dp[j]%C ) %C와 같다. 모듈러 연산의 분배법칙은 덧셈+, 뺄셈-, 곱셈* 에만 적용이 가능하고 나머지 연산에 대해서는 분배법칙을 적용할 수 없다.