[programmers][월간 코드 챌린지 시즌1] 짝수 행 세기

문제 : programmers.co.kr/learn/courses/30/lessons/68647

---

0과 1로 이루어진 2차원 배열이 주어질 때 조건을 만족하며 만들 수 있는 2차원 배열의 경우의 수를 구하여라.

1. 모든 원소는 0, 1이다.

2. 입력으로 주어지는 배열의 각 열이 가진 1의 개수와 새롭게 만드는 배열의 각 열의 1의 개수는 같다.

3. 각 행의 1의 개수는 짝수이다.

 

경우의 수의 10^7 + 19로 나눈 나머지를 반환해라.

---

dp로 풀었다.

 

let, n = 입력 배열의 행의 수, m = 입력 배열의 열의 수.

dp[column][num] = arr[0~n][0~column]까지 1,2번 조건을 만족하면서 num개의 행이 짝수인 배열을 만들 수 있는 경우의 수

dp 배열은 위와 같다. dp 배열의 인덱스는 조건에서 언급한 변수를 선택하는 것이 좋다.

3번 조건에서 각 행의 1의 개수는 짝수라고 했다.

dp[column][num]에서 dp[column+1][nextNum]을 만들 수 있다.

dp[column][num]에서 arr배열의 column+1 열을 추가하면서 dp[column+1][nextNum]을 만들게 될 것이다.

우리가 dp[column][num]에서 알 수 있는 값들은 짝수 행(행들 중에 1의 개수가 짝수개인 행을 앞으로 짝수행이라 하겠다. 반대의 경우 홀수행)의 개수, dp[column][num] 값이다.

 

만약 짝수행의 column+1열에 1을 추가하는 경우 해당 짝수행은 홀수 행이 될 것이다.

반대로 홀수행의 column+1열에 1을 추가하는 경우 해당 홀수행은 짝수 행이 될 것이다.

이제 짝수행들(num개) 중 k개의 행에 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

---

과거에는 확률이 뛰어난 천재들만 이해하던 개념이라는 글을 본 적이 있다. 끄어어... 머리야 돌아라..!

해설을 보고도 며칠을 헤맸다. 당 땡겨 당땡겨~