Programmers. 짝수 행 세기

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 짝수 행 세기

문제 풀이

처음엔 순열 조합으로 쉽게 풀 수 있지 않을까 생각했지만 도저히 풀리지 않아 라이트업을 참고하였고 아주 괴랄한 dp문제임을 알 수 있었다. 아마 나 혼자 생각해서든 절대로 풀 수 없으리라 생각한다.

우선 각 열의 1의 개수에 대해 카운트하여 저장하는 배열을 하나 생성한다. 그리고 적당히 1을 선택하는 경우의 수를 구해야 하므로 이항계수를 계산하는 함수도 정의해야 한다. 행에 대해 선택할 것이고 행의 입력 제한이 300인 것으로 보아 효율적인 DP연산으로 구해야 하며 사전에 2차원 배열로 저장해두면 나중에 조회할 때 용이하겠다. R + 1 * R + 1크기의 배열을 선언해 이항계수 값을 채워주자(전체 행에 대해 c개의 행을 선택하는 경우의 수)

def solution(a):
    MOD = 10 ** 7 + 19
    R, C = len(a), len(a[0])
    pascal = [[0] * (R + 1) for _ in range(R + 1)]
    def comb(n, c):
        if n == c or c == 0:
            pascal[n][c] = 1
            return 1
        if pascal[n][c] > 0:
            return pascal[n][c] % MOD
        pascal[n][c] = (comb(n - 1, c - 1) + comb(n - 1, c)) % MOD
        return pascal[n][c]
    for i in range(R + 1):
        for j in range(i + 1):
            comb(i, j)
    cnt = []
    for j in range(C):
        o = 0
        for i in range(R):
            if a[i][j] == 1:
                o += 1
        cnt.append(o)

이제 DP 배열을 정의해야 하는데 여기가 어마어마하다. 우선 짝수행과 홀수행에 대해 개념을 숙지해야 한다.

• 짝수행 : 행에 존재하는 1의 개수가 짝수이거나 0
• 홀수행 : 행에 존재하는 1의 개수가 홀수(전체행 - 짝수행)

DP배열을 row는 주어진 2차월 배열의 column에 대응되며 DP배열의 col은 각 열까지에 대해 col만큼의 짝수행을 갖는 경우의 수를 의미한다. 따라서 DP 배열의 초항은 1번째 col에 대해 ${R}C{cnt}$가 될 것이다. 그릐고 짝수행의 개수는 전체 행의 개수에서 1번 열의 1의 개수를 뺀 값으로 R - ​cnt[0]이다.

이제 1번역부터 C-1번열까지 순회하되(i에서 i + 1번 열의 값 완성) DP 배열의 갱신을 위해 0부터 R까지의 짝수행을 갖는 경우의 수를 다시 순회해야 한다.

이전열의 짝수행에 대해 경우의 수가 없다면 skip하고 0부터 현재 열의 r의 개수에 대해 다음 열이 가질 수 있는 짝수행의 개수를 알 수 있다.

• 현재 짝수행에 k개를 선택해 배치하면 홀수행이 되므로 나머지는 그대로 짝수행
• 현재 열의 1의 개수 중 짝수행에 배분한 k개 외 나머지는 홀수행에 배치되어 짝수행이 됨

만약 다음 열에서 만들어지는 짝수행의 개수가 범위를 넘어서거나 현재 짝수행이 선택된 k보다 작으면 skip, 다음 열에 짝수행이 발생하는 경우의 수는 현재 행에서 n-k개를 선택하는 방법(n-k나 k나 이항계수 값은 똑같기 때문에 k로 바꿔도 됨) * 현재 홀수행에서 나머지 1(n - k)을 선택하는 방법을 곱한 값이며 따라서 다음 열에서 생성될 짝수행만큼 생성될 경우의 수는 이전 열의 현재 짝수행의 경우에서 짝수행이 발생할 경우의 수를 곱한 값이다.

    dp = [[0 for _ in range(R + 1)] for _ in range(C + 1)]
    dp[1][R - cnt[0]] = pascal[R][R - cnt[0]]
    for c in range(1, C):
        for r in range(R + 1):
            if dp[c][r] == 0:
                continue
            for o in range(cnt[c] + 1):
                nxt = (r - o) + (cnt[c] - o)
                if nxt > R or r < o:
                    continue
                case = (pascal[r][o] * pascal[R-r][cnt[c] - o]) % MOD
                dp[c + 1][nxt] += (dp[c][r] * case) % MOD
    return dp[C][R]

python 코드

def solution(a):
    MOD = 10 ** 7 + 19
    R, C = len(a), len(a[0])
    pascal = [[0] * (R + 1) for _ in range(R + 1)]
    def comb(n, c):
        if n == c or c == 0:
            pascal[n][c] = 1
            return 1
        if pascal[n][c] > 0:
            return pascal[n][c] % MOD
        pascal[n][c] = (comb(n - 1, c - 1) + comb(n - 1, c)) % MOD
        return pascal[n][c]
    for i in range(R + 1):
        for j in range(i + 1):
            comb(i, j)
    cnt = []
    for j in range(C):
        o = 0
        for i in range(R):
            if a[i][j] == 1:
                o += 1
        cnt.append(o)
    dp = [[0 for _ in range(R + 1)] for _ in range(C + 1)]
    dp[1][R - cnt[0]] = pascal[R][R - cnt[0]]
    for c in range(1, C):
        for r in range(R + 1):
            if dp[c][r] == 0:
                continue
            for o in range(cnt[c] + 1):
                nxt = (r - o) + (cnt[c] - o)
                if nxt > R or r < o:
                    continue
                case = (pascal[r][o] * pascal[R-r][cnt[c] - o]) % MOD
                dp[c + 1][nxt] += (dp[c][r] * case) % MOD
    return dp[C][R]