MOD 연산의 특성 (분배 법칙)

덧셈

(A+B)%C=(A%C+B%C)%C

 

ex)

(20+6)%3=26%3=2

(20%3+6%3)%3=(2+0)%3=2

 

뻴셈

(A-B)%C=(A%C-B%C)%C

 

ex)

(20-6)%3=14%3=2

(20%3-6%3)%3=(2-0)%3=2

 

곱셈

(A*B)%C=(A%C)*(B%C)%C

 

ex)

(20*6)%3=120%3=0

(20%3)*(6%3)%3=(2*0)%3=0

 

나눗셈

(A/B)%C != (A%C)/(B%C)%C => 성립하지 않음

 

ex)

(20/6)%3=3%3=0

(20%3)/(6%3)%3=(2/0)%3=>분모 0 X 

 

MOD 연산은 덧셈, 뻴셈, 곱셈에 대해서 분배 법칙이 성립한다.

=>즉, 정답을 구한 뒤 % 연산을 하는 것이 아닌, 각 단계마다 %연산을 하면서 문제를 풀도록 하자.

 

백준 11051번 (이항 계수 2) 문제에 이를 적용해보자.

문제:

자연수 N과 정수 K가 주어졌을 때 이항 계수 (N K)를 10007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력:

첫쨰 줄에 N과 K가 주어진다. (1<=N<10000, 0<=K<=N)

출력:

(N K)를 10007로 나눈 나머지를 출력한다.

1) 올바르지 않은 풀이.

public static void main(String[] args) throws Exception{

    Scanner sc = new Scanner(System.in);

    int N = sc.nextInt();

    int K = sc.nextInt();

    int D[][] = new int[N+1][N+1];

    for(int i=0; i<= N; i++){

      D[i][1]=i;

      D[i][0]=1;

      D[i][i]=1;

    }

    for(int i=2; i<=N; i++){

      for(int j=1; j<i; j++){

        D[i][j] = D[i-1][j] + D[i-1][j-1];

        D[i][j] = D[i][j];

      }

    }

    System.out.println(D[N][K]%10007); =>마지막에 한번에 %연산을 시도함.

}  => 실패 : 중간 단계에서 이미 범위 초과

 

2) MOD연산의 분배법칙의 성질을 이용한 풀이

public static void main(String[] args) throws Exception{

    Scanner sc = new Scanner(System.in);

    int N = sc.nextInt();

    int K = sc.nextInt();

    int D[][] = new int[N+1][N+1];

    for(int i=0; i<= N; i++){

      D[i][1]=i;

      D[i][0]=1;

      D[i][i]=1;

    }

    for(int i=2; i<=N; i++){

      for(int j=1; j<i; j++){

        D[i][j] = D[i-1][j] + D[i-1][j-1];

        D[i][j] = D[i][j]%10007; => 매 단계마다 % 연산을 해주기

      }

    }

    System.out.println(D[N][K]);

} 

**정답을 ~로 나눈 나머지를 출력하시오. => 단계마다 %연산해주는 방법을 먼저 시도해보자.