EunSung.log

짝수 행 세기

6 min read

문제 정보

풀이

a의 i번째 열과 b의 i번째 열에 들어 있는 1의 개수가 같다는 조건과 b의 각 행에 들어 있는 1의 개수는 짝수 (0 포함) 라는 조건 때문에, 앞선 열의 1의 배치에 따라서 뒤의 열의 1의 배치가 제한된다.

즉, 앞에서의 계산 결과를 기반으로 현재의 결과를 계산해야 한다는 것이므로 동적계획법을 사용해야 하는 문제다.

배열 dp를 다음과 같의 정의한다.

  • dp[i][j]: i번째 열까지 고려했을 때 1의 개수가 짝수 개인 행이 j개인 경우의 수

이제 dp[i][j]를 계산하는 방법에 대해 살펴보자.

dp[i][j]를 계산할 땐 i-1번째 열까지 1의 배치가 끝난 상태다. 그 중엔 1의 개수가 짝수 개인 행(이하 ‘짝수행’)도 있을 것이고, 1의 개수가 홀수 개인 행(이하 ‘홀수행’)도 있을 것이다.

그리고 그런 행들에 전체 o개의 1을 배치해야 하는 상황이라고 하자.

이때 짝수행에 1이 배치되면 해당 행은 홀수행으로, 반대로 홀수행에 1이 배치되면 해당 행은 짝수행으로 변한다.

우리가 궁금한 건 결국 새로운 짝수행의 개수이고, 이는 “1이 배치되지 않은 짝수행의 수” + “1이 배치된 홀수행의 수”로 계산된다.

그렇기에 새로운 짝수행의 개수는 (j - k) + o - k로, 정리하면 j + o - 2k가 된다. (여기서 j는 기존의 짝수행의 개수)

이때의 경우의 수는 개이다.

코드

import java.util.*;
 
class Solution {
	private static final int MOD = (int) 1e7 + 19;
	
	public int solution(int[][] a) {
		int row = a.length;
		int col = a[0].length;
		
		// 각 열마다 1이 몇 개 들었는지 확인
		int[] numOfOne = new int[col];
		for (int j = 0; j < col; j++) 
			for (int i = 0; i < row; i++)
				if (a[i][j] == 1) numOfOne[j]++;
				
		// 조합 계산
		long[][] comb = new long[row + 1][];
		for (int i = 0; i <= row; i++) {
			comb[i] = new long[i + 1];
			comb[i][0] = comb[i][i] = 1;
			for (int j = 1; j < i; j++)
				comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % MOD;
		}
		
		long[][] dp = new long[col][row + 1];
		
		// 첫 번째 열 초기화
		dp[0][row - numOfOne[0]] = comb[row][row - numOfOne[0]];
		
		for (int i = 1; i < col; i++) {
			int o = numOfOne[i]; // 이번 열에 들어가야 하는 1의 개수
			for (int evenNum = 0; evenNum <= row; evenNum++) {
				if (dp[i - 1][evenNum] == 0) continue; // 경우의 수가 없는 상태면 건너뜀
				
				for (int k = 0; k <= o; k++) {
					if (k > evenNum) break;
					if (o - k > row - evenNum) continue;
					
					int newEvenNum = evenNum + o - 2 * k;
					
					long ways = comb[evenNum][k] * comb[row - evenNum][o - k] % MOD;
					dp[i][newEvenNum] += dp[i - 1][evenNum] * ways % MOD;
				}
			}
		}
		
		return (int) dp[col - 1][row];
	}
}

비고

  • comb와 dp를 int형으로 뒀었는데 몇몇 테스트 케이스에서 통과하지 못했다. 자료형을 long으로 바꾸고 통과한 걸 보니 아마 오버플로우가 났던 것 같다.
  • 원래는 newEvenNum를 검증하는 코드가 있었다.
    • if (newEvenNum < 0 || newEvenNum > row) continue;
    • 그러나 중복 검증인 것 같아 확인해보니, 앞선 두 조건문을 통과한 시점에서 저 두 경우가 나올 수 없어 조건문을 삭제했다.
      • 앞선 두 조건문을 통과했으므로 k <= evenNum, o - k <= row - evenNum
      • newEvenNum = evenNum + o - 2k
      • newEvenNum < 0
        • k <= evenNum에서 k를 이항하면 evenNum - k >= 0
        • newEvenNum은 evenNum - k + (o - k)
        • 여기서 k는 1 이상 o이하의 값이므로 o - k >= 0
        • 따라서 newEvenNum은 양수 + 양수 이므로 newEvenNum >= 0
        • 그러므로 newEvenNum < 0인 경우는 없음
      • newEvenNum > row
        • o - k <= row - evenNum에서 evenNum을 이항하면 evenNum + o - k <= row
        • 여기서 k는 양수이므로 evenNum + o - 2k < evenNum + o - k가 성립
        • 즉 evenNum + o - 2k < evenNum + o - k <= row이므로 newEvenNum > row 인 경우는 없음
    • 차근차근 생각해볼 수 있어서 할 수 있었던 결정인지라 실제 코테 환경이었다면 할 수 있었을지 의문이다.

백링크