짝수 행 세기

• DP
• 짝수행? 홀수행?
• DP[1]
• DP[2]
• 일반화
  • 짝수행에 더해줄 1의 개수
  • 기존의 짝수행개수에 1이 더해져 만들어지는 새로운 짝수행의 개수
  • 새로 만들어지는 짝수행 개수의 경우의 수
  • DP

from collections import defaultdict
from math import comb
from functools import lru_cache
@lru_cache(maxsize=None)
def C(n,k): return comb(n,k)
def solution(a):
    one_cnt = [sum(ones) for ones in zip(*a)] # 각열 1의 갯수
    DP = defaultdict(int,{(rows := len(a))-one_cnt[0]:comb(rows, one_cnt[0])}) # 1열까지 계산한 DP
    for ones in one_cnt[1:]: # DP[2][j] 부터 계산
        next_DP = defaultdict(int)
        for even_rows in DP:
            odd_rows = rows-even_rows
            for add_one in range(max(0,ones-odd_rows), min(ones,even_rows)+1): # range 범위는 미만이기때문에 +1
                next_DP[even_rows+ones-2*add_one] += DP[even_rows] * C(even_rows, add_one) * C(odd_rows, ones-add_one)%(10**7+19)
        DP = next_DP
    return DP[rows]

DP

DP로 풀어야하는 문제이니 만큼 DP의 의미를 파악해야한다.

DP[i][j] = K = i 열까지 계산했을 때 j개의 짝수행을 가지는 B의 개수는 K개다.

DP의 뜻이 무슨말인지 감이 안잡혀도 괜찮다. 다만 조건을 만족하는 B의 개수를 이렇게 열을 늘려가며 찾아가겠다는 방식만 기억하고 가자.

짝수행? 홀수행?

1의 개수가 짝수개 만큼 있는 행들을 짝수행, rows - 짝수행 을 홀수행 이라고 칭한다.

DP[1]

DP의 뜻을 다시한번 보자

DP[i][j] = K = i 열까지 계산했을 때 j개의 짝수행을 가지는 B의 개수는 K개다.

그렇다면 i = 1 일때의 뜻은

DP[1][j] = K = 1 열까지 계산했을 때 j개의 짝수행을 가지는 B의 개수는 K개다.

첫째열까지는 짝수행은 A의 1열의 0의 개수만큼 가질 수 있고, 0의 개수만큼 짝수행을 가지는 경우의 수는 \(\frac{rows!}{1의개수! \cdot 0의개수!}\\\)

가 된다(중복있는 순열 공식). 그 외에 다른 짝수행개수는 나올 수 없다.

DP[2]

1열까지 계산한 결과 이러한 결과값이 나온다. A의 2번째 열은 1을 1개 가지고있고, 우린 현재 짝수행 2개짜리가 6개있다.

이렇게 짝수행2개짜리 열에 1을 추가하는 방법은 총 몇가지가 있을까?

짝수행에 1을 0개 추가, 나머지 1 의 개수 1개를 홀수행에 추가

• 2개짜리 짝수행에서 짝수행(2) - 짝수행에 추가한 1의 개수(0) + 홀수행에 추가한 1의 개수(1) = 3개짜리 짝수행 탄생

짝수행에 1을 1개 추가, 나머지 1 의 개수 0개를 홀수행에 추가

• 2개짜리 짝수행에서 짝수행(2) - 짝수행에 추가한 1의 개수(1) + 홀수행에 추가한 1의 개수(0) = 1개짜리 짝수행 탄생

DP[2][1]과, DP[2][3]이 만들어졌다. 그러면 이렇게 짝수행이 바뀐 경우의 수가 몇개일까?

DP[짝수행개수 - 추가할 1의 개수 + 현재열의 1의 개수 - 추가할 1의 개수]

• 짝수행개수의 경우의 수
• 1이 더해질 짝수행 개수를 고르는 경우의 수
• 1이 더해질 홀수행 개수를 고르는 경우의 수

이 3가지를 다 곱해주면된다.

이런식으로 DP를 갱신해나가며 DP[cols][rows]를 구하면 된다.

일반화

행의 개수 = rows

짝수행 개수 = even_rows

홀수행 개수 = odd_rows

다음열 1의 개수 = ones

짝수행에 추가할 1의 개수 = add_one

짝수행에 더해줄 1의 개수

짝수행에 더해줄 add_one의 최소값을 0 으로 하려 했지만, 만약에 ones > odd_rows 인경우엔 짝수행에 최소 ones - odd_rows 개를 더해주어야한다. 다시말하면 add_one의 최소값은 max(0, ones-odd_rows) 가된다.

(이런경우에)

반대로 add_one의 최대값은 min(ones, even_rows)가 된다.

add_one의 최소값 : 1을 더할 짝수행의 최소개수

add_one의 최대값 : 1을 더할 짝수행의 최대개수

기존의 짝수행개수에 1이 더해져 만들어지는 새로운 짝수행의 개수

기존 짝수행개수(even_rows)에서 새로 만들어지는 짝수행 개수

• even_rows - add_one + ones - add_one
• even_rows + ones - 2*add_one

새로 만들어지는 짝수행 개수의 경우의 수

1이 추가될 even_rows선택 경우의 수 x 1이 추가될 odd_rows선택 경우의 수 x even_rows 경우의수

C(even_rows, add_one) * C(odd_rows, ones-add_one)*DP[even_rows]

DP

새로 만들어지는 even_rows에 대해서만 계산이 필요하므로, 굳이 2x2 배열을 만들 필요없이 dictionary을 이용하는것이 메모리적으로 이득이다.

from collections import defaultdict
from math import comb
from functools import lru_cache
@lru_cache(maxsize=None)
def C(n,k): return comb(n,k)
def solution(a):
    one_cnt = [sum(ones) for ones in zip(*a)] # 각열 1의 갯수
    DP = defaultdict(int,{(rows := len(a))-one_cnt[0]:comb(rows, one_cnt[0])}) # 1열까지 계산한 DP
    for ones in one_cnt[1:]: # DP[2][j] 부터 계산
        next_DP = defaultdict(int)
        for even_rows in DP:
            odd_rows = rows-even_rows
            for add_one in range(max(0,ones-odd_rows), min(ones,even_rows)+1): # range 범위는 미만이기때문에 +1
                next_DP[even_rows+ones-2*add_one] += DP[even_rows] * C(even_rows, add_one) * C(odd_rows, ones-add_one)%(10**7+19)
        DP = next_DP
    return DP[rows]