[프로그래머스/LV4] 짝수 행 세기 (Python)

Problem : https://school.programmers.co.kr/learn/courses/30/lessons/68647

프로그래머스

 

Status : Solved

 

Time : 01:14:41

 

---

 

문제 설명

 

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

• b의 모든 원소는 0 아니면 1입니다.
• a의 행/열의 개수와 b의 행/열의 개수가 같습니다. (= a와 b의 크기가 같습니다.)
• `i = 1, 2, ..., (a의 열의 개수)`에 대해서 a의 i번째 열과 b의 i번째 열에 들어 있는 1의 개수가 같습니다.
• b의 각 행에 들어 있는 1의 개수가 짝수입니다. (0도 짝수입니다.)

 

입력 및 출력

 

제한사항

• a의 행의 개수는 1 이상 300 이하입니다.
  • a의 각 행의 길이는 1 이상 300 이하로 모두 동일합니다.

 

입출력 예

a	result
[[0,1,0],[1,1,1],[1,1,0],[0,1,1]]	6
[[1,0,0],[1,0,0]]	0
[[1,0,0,1,1],[0,0,0,0,0],[1,1,0,0,0],[0,0,0,0,1]]	72

 

 

---

 

풀이

 

오늘의 꿀팁 : 출력 크기가 MOD 연산을 써야 할 정도로 매우 크다면 DP를 시도해볼것.

 

DP로 푸는 것 까지는 좋은데... 문제는 어떻게 적용할지이다. 여기서 많은 시간을 소비했었다.

 

우선, i번째 열까지 배열했을 때, 짝수 행의 개수가 j개인 경우를 DP[i][j]로 정의하자. i = 0일때, 즉 1 개수 리스트의 첫번째 값 one_list[0]을 배열했을 때, 0의 개수는 col - one_list[0]이 되고, 초기값 DP[0][col - one_list[0]]은 C (col, one_list[0])이 된다. 즉 0이 col - one_list[0]개, 1이 one_list[0]개 있을 때 숫자들간의 순서를 고려하지 않고 배열하는 경우의 수와 같다.

 

이제 다음을 생각해보자. DP[i][j]에선 짝수 행이 j개, 홀수 행이 col - j개 존재한다. 또한 one_list[i+1]에는 1이 tot_num 개 존재한다고 가정하자.

 

• 1은 당연히 홀수, 0은 짝수이다. 따라서 짝수 개 행에 1을 더하면 홀수, 홀수 개 행에 1을 더하면 짝수가 된다.
  • 짝수 + 짝수  = 짝수 / 홀수 + 홀수 = 짝수 / 짝수 + 홀수 = 홀수 를 생각해보자.
• tot_num개의 1 중 k개의 1을 짝수에, tot_num개의 1을 홀수에 집어넣는 경우를 생각해 볼 수 있다.
  • 그렇다면, j개 중 k개는 홀수가 되며, 나머지 j + k는 짝수가 된다. 반면 col - j 개 중 tot_num - k개는 짝수 행이 되며, 나머지 col - j - tot_num + k 개는 그대로 홀수일 것이다.

적용 전 / 적용 후	짝수	홀수
짝수	j - k	k
홀수	tot_num - k	col - j - tot_num + k

• 즉 적용 후 총 짝수의 개수는 j + tot_num - 2 * k개가 된다! 즉 DP[i+1][ j + tot_num - 2 * k] 에 직접적으로 영향을 준다!
• 다시 여기서. 두 번의 조합 계산이 필요하다.
  • 적용 전의 짝수 행 j개에 k개를 순서 상관 없이 배치하는 경우의 수는 C(j, k)이다.
  • 적용 전의 홀수 행 col - j개에 tot_num - k개를 순서 상관 없이 배치하는 경우의 수는 C(col - j, tot_num - k)이다.
• 즉 최종적인 식은 다음과 같이 나타낼 수 있다!

DP[i+1][ j + tot_num - 2 * k] += DP[i][j] *  C(j, k) * C(col - j, tot_num - k)

 

여기서, 짝수 행에 배치하고자 하는 1이 현재 짝수행보다 크거나, 홀수 행에 배치하고자 하는 1이 현재 홀수 행보다 적은 예외상황을 반드시 제외하자. 모든 i에 대해 이를 반복하면 최종적으로 모든 1을 배치했을 때 모든 행이 짝수인 경우의 수가 도출된다.

 

또한, 조합 계산 역시 최대 n이 300이므로 엄청나게 큰 값이 도출된다. 이를 일일히 직접 계산하는것보다는, 이 역시 메모이제이션을 통하여 계산해나가는 것이 좋다.

 

 

• combination : 조합값을 구하는 함수. 조합값은 조합의 성질을 이용해 재귀적으로 구할 수 있다. 이미 메모이제이션으로 알고 있는 값일 경우 그 값을 그대로 반환한다. 모드 연산에 주의하자.
• count_1s : 초기 a 리스트의 각 열의 1의 개수를 저장하여 반환하는 함수이다.
• make_dp : 앞서 풀이한 DP를 통해 모든 DP 리스트를 채우는 함수이다.
• solve : 메인함수. count_1s로 생성한 1의 개수 리스트를 make_dp에 전달하고, 반환된 DP에서 정답값을 찾아 반환한다.

 

 

풀이 코드

import sys
sys.setrecursionlimit(10000000)

MOD = 10**7 + 19
comb_list = [[0]*301 for _ in range(301)]

def combination(n, r) :
    if n == 1 or n == r or r == 0 :
        return 1
    if comb_list[n][r] :
        return comb_list[n][r]
    
    comb_list[n][r] = ( combination(n-1,r-1) % MOD + combination(n-1,r) % MOD ) % MOD
    return comb_list[n][r]
        

def count_1s(a, col, row) :
    result = list()
    for i in range(row) :
        cnt = 0
        for j in range(col) :
            cnt += a[j][i]
        result.append(cnt)
    
    return result

def make_dp(col, row, lst) :
    dp = [[0]*(col+1) for _ in range(row)]
    dp[0][col - lst[0]] = combination(col, lst[0])
    
    for i in range(row-1) :
        for j in range(col+1) :
            if dp[i][j] :
                tot_num = lst[i+1]
                for k in range(min(tot_num, j)+1) :
                    if col - j < tot_num - k :
                        continue
                    even = j + tot_num - 2*k
                    dp[i+1][even] += ( dp[i][j] % MOD * combination(j, k) * combination(col-j, tot_num - k) ) % MOD
    
    return dp

def solution(a):
    col, row = len(a), len(a[0])
    one_list = count_1s(a, col, row)
    dp = make_dp(col, row, one_list)

    return dp[-1][-1]

풀이 완료~