왜 정답을 나눈 나머지를 출력하라고 할까? - 나머지 연산

 

요즘 dp 문제를 풀면서 정답을 특정 값으로 나눈 나머지를 출력하라는 조건을 많이 발견했다.

 

다른 사람들의 풀이를 보고 블로그들을 찾아보면서 다음과 같은 성질을 활용한다는 것을 알 수 있었다.

 

 

 

(A + B) % M = (A % M + B % M) % M

 

 

 

최종적으로 구한 dp 배열에 특정 값들을 합한 결과를 출력하고는 한다.

 

그런데 dp 배열을 구하는 과정에서 매번 그 값들의 나머지를 구해줘도 동일한 결과값이 나온다는 말이다.

 

실제로 그러한지 간단한 소스코드로 구현해보았다.

 

 

 

#include <iostream>
#include <limits.h>	// INT_MAX 상수
using namespace std;

int mod = 1e+7;	// 10^7

int main(){
    long a = INT_MAX, b = INT_MAX;
    cout << (a + b) % mod << endl;
    cout << (a % mod + b % mod) % mod << endl;
    return 0;
}

 

 

실행해보니 두 케이스 모두 4967294 로 동일한 결과값이 나왔다.

이 식이 성립한다는 것을 확인했으니 dp 문제 풀이에 적용하면 되겠다는 확신이 든다.