[lv4][해설 안봄] 짝수 행 세기

모든 수가 0 또는 1로 이루어진 2차원 배열 a가 주어집니다. 다음 조건을 모두 만족하는 2차원 배열 b의 경우의 수를 (107 + 19)로 나눈 나머지를 return 하도록 solution 함수를 완성해주세요.

 

 

우선 각 열에 들어갈 숫자의 1의 갯수는 문제에서 구할 수 있다.

 

이제 문제는 각 행의 1의 갯수가 짝수개가 되야 한다는 것이다.  또한 문제에서 짝수개가 나오면 떠올려야 하는게 짝수개에서 한개를 더하면 홀수개가 된다는 것이다.

이 점을 이용하면 비트마스킹을 쓰면 될 것같다. 1열에서 2열로 이동하면서   dp[1000] = dp[1010] * dp [0010]  이런식으로 말이다. 그러나 여기서 최대   n은 300이고, 2^300 * 300 의 시간이 걸릴뿐더러 비효율 적이다.

 

내가 푼 방식은 dp[n][그동안의  1의 갯수의 총합이 홀수개인 행의  갯수] 로 푸는 것이다.

예를 들면 밑의 그림에서는 dp[3][1] 을 계산하는 것이 된다. 1행 : 홀수  (2행,3행,4행) : 짝수 (0개도 짝수)

 

 

 

 

 

n-1번째에서 홀수갯수의 dp : dp[n - 1][파랑길이]  라고 해보자.  

파란색에서 초록색을 더했을 때, 빨간색부분은  홀수개에서 1이 더해지므로 짝수개가 된다. 

 

결국 홀수의 갯수는 남은 갯수가 된다. 남은 갯수는  파란길이 + 초록길이 - 2 * (빨간길이) 이다.  빨간부분은 겹치기 때문에 2 번 제거한다.  파란색 홀수의 갯수를  i라고 하고,  초록색 1의 갯수를 j, 빨간색 겹치는 홀수 갯수를 k 라고 하면 dp[n][i + j - 2k] 에 대해 구할 수 있다.   그리고 빨간색이 올 수 있는 경우의 수를 계산해보면, 파란색의 갯수에서 빨간색을 선택할 수 있는 경우의 수 : i C k 이다.   또한  초록색이 추가되면서 1이 추가될 수 있는 경우의 수를 구해본다. 1이 추가 될 수 있는 곳의 전체 갯수는  nY - 파란색의 갯수이다. 여기서 j - k 개를 선택하면 된다.  nY- i  C j - k  

 최종적으로      dp[n][i + k - 2k] = i C k * (nY-i)C(j - k) * dp[n- 1][i]

 

 

 

그럼 이제 i  : 1부터 열의 갯수까지 for문을 돌면서 ->  j : 1부터 행의 갯수까지 for문을 돌면서 -> k: 가능한 겹치는 부분의 갯수까지 for문을 돈 후, dp[n][0] 이 답이 될 것이다. ( 행의 1의 갯수가 모두 짝수개여야 하므로, 홀수개가 0이여야 한다. )