Programmers 68647: 짝수 행 세기

모든 수가 0 또는 1로 이루어진 2차원 배열 a가 주어질 때, 2차원 배열 b의 경우의 수를 (10^7 + 19)로 나눈 나머지를 구하는 문제이다.

 

문제 조건

• b의 모든 원소는 0 또는 1이며 a와 b의 크기가 같다
• a의 i번째 열과 b의 i번째 열에 들어 있는 1의 개수가 같다.
• b의 각 행에 들어 있는 1의 개수가 짝수이다. (0도 짝수)

일단... 경우의 수를 ~~로 나눈 나머지를 구하라고 했으니 이 수가 엄청나게 클 것이고 그냥 구하면 시간 초과가 날 것이라는 것을 알 수 있다.

대개 이렇게 결과값의 나머지를 구하라는 문제는 dp로 푸는데, dp를 어떻게 적용하면 좋을지 생각해 봤다.

 

dp[i][j]: (0, 0) ~ (i, j)까지 조건에 맞는 b를 만들 수 있는 경우의 수라고 정의하자.

 

만약 행들 중 1의 개수가 짝수이면 1을 더하면 홀수가 될 것이고, 홀수이면 1을 더하면 짝수개가 될 것이다.

열 하나를 추가해서 새롭게 만들어지는 배열은 몇 개의 짝수행을 가지고 있을 것인가. 그리고 만들 수 있는 경우의 수는 어떻게 될까.

 

기존에 가지고 있던 짝수행의 개수는 num개 였고 k개의 행에 1을 추가한다고 했기 때문에 k개의 행이 홀수행이 될 것이고 남은 num-k개가 여전히 짝수행일 것이다. 이 경우의 수는 기존 짝수행의 개수 num개 중 k개를 넣을 것이기 때문에 조합 (num)C(k) 이다.

기존에 가지고 있던 홀수행은 n-num개(전체 배열의 행 크기 - 짝수 행 크기) 일 것이다. 조건 2에 의해 입력배열에서  column+1 열의 1의 개수를 알 수 있고 이를 oneCnt라 하자. oneCnt 중 k개는 짝수행에 넣을 것이고 남은 oneCnt - k개의 1을 홀수행에 넣을 것이다. 따라서 oneCnt-k개가 짝수행이 될 것이다. 이 경우의 수는 기존 홀수행의 개수 n-num개 중 oneCnt - k개를 넣을 것이기 때문에 조합 (n-num)C(oneCnt-k)가 될 것이다. 

 

위와 같이 짝수행, 홀수행의 경우를 독립사건으로 보고 각자의 경우의 수를 구했으면 두 경우의 수를 곱한 결과에 dp[column][num]을 곱한 결과가 우리가 구하고자 하는 dp[column+1][(num-k) + (oneCnt-k)] 값이 된다.

 

for(column을 1~m까지)
  for(num을 0에서 n까지)
    for(k를 0에서 oneCnt까지)
       // 점화식
       dp[column+1][(num-k) + (oneCnt-k)] = SUM[dp[column][num] * (num)C(k) * (n-num)C(oneCnt-k)]

설명에서는 생략했지만 dp 배열에 들어가는 계산에는 10^7 + 19 나머지 연산을 해서 변수값 범위를 넘어가지 않도록 주의한다. 

 

시간복잡도는 O(N^2 * M)

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/programmers/%EC%9B%94%EA%B0%84%20%EC%BD%94%EB%93%9C%20%EC%B1%8C%EB%A6%B0%EC%A7%80%20%EC%8B%9C%EC%A6%8C1/%EC%A7%9D%EC%88%98%20%ED%96%89%20%EC%84%B8%EA%B8%B0.cpp