[프로그래머스/C++] 짝수 행 세기

 

 

문제

문제 설명

 

 

 

풀이

 

[문제 풀이]

 

이 문제는 아이디어가 정말 안 떠올랐다.

규칙을 발견해 조합으로 해결이 될 것처럼 보였는데, 아무리 고민을 해도 짝수개의 열을 만드는 작업이 잘 안됐다.

 

그러다가 다른사람의 질문에서 홀수와 짝수라는 힌트를 얻고 방법이 떠올라 문제를 해결할 수 있었다.

 

먼저 문제의 조건에서 a 배열의 특정 열에 1이 포함된 개수와 b 배열의 특정 열에 있는 1의 개수가 같아야 된다.

 

그렇기 때문에 이 조건을 만족하기 위해 a의 각 열 당 몇 개의 1이 있는지 개수를 센 다음에 그 열에 있는 1들의 개수만큼 각 행에 배치를 해주면 된다.

 

여기서 1의 개수를 배치하는 방법을 조합으로 나타낼 수 있는데, n개의 행에서 1을 배치할 r개의 행을 뽑는다면 이는 nCr의 조합으로 나타낼 수 있다.

 

이 다음으로 고려해야 할 것은 행이 전부 짝수인지 홀수인지 어떻게 판단할지이다.

 

1이 짝수개 있는 행에 1을 배치한다면 1이 홀수개가 있는 행이 된다.

반대로 1이 홀수개 있는 행에 1을 배치한다면 1이 짝수개가 있는 행이 된다.

 

아래  4x4행렬을 예로 든 그림을 보면 더 이해가 쉽다.

 먼저 첫 열에 있는 1의 개수가 2라고 하자.

그러면 처음에는 모든 행에 1이 없는 상태에서 시작하므로 4개의 짝수 행에 1을 배치할 2개의 행을 고르는 것과 같다.

 

그 다음의 열은 1을 1개 배치할 수 있다.

여기서 짝수 행에 1을 배치하는 방법이 있고, 홀수 행에 1을 배치하는 방법이 있다.

 

짝수행에 1을 배치하는 경우는 짝수 행이 2개였으므로 2C1을 곱하고, 홀수 행이 1개 늘어나게 된다.

그러므로 홀수 행이 3인 곳에 경우의 수를 저장한다.

 

홀수행에 1을 배치하는 경우도 홀수 행이 2개였으므로 2C1을 곱한다. 이후 홀수 행이 1개 줄어들었으므로, 홀수 행이 1인 곳에 경우의 수를 저장한다.

 

이렇게 경우의 수를 구하는 과정은 다음과 같이 나타낼 수 있다.

 

1. 총 행의 개수를 row, 현재 홀수 행의 개수를 odd, 다음열에서 배치할 1의 개수를 a라고 하자.

(짝수행의 개수는 row-odd가 된다)

 

2. 홀수행에 b개의 1을 배치한다면, 이 때 경우의 수는 다음과 같고, 변경된 홀수 행의 수는 odd-b가 된다

$${}_{odd}{\rm C}_{b} \times {}_{row-odd}{\rm C}_{a-b}$$

 

이 과정을 반복하면서 각 열에서 1을 배치할 수 있는 경우의 수를 저장한다.

그리고 모든 열까지 이 작업을 진행했을 때, 홀수 행의 수가 0인 경우의 수를 return하면 된다.

 

​

[아이디어 정리]

1. 각 열당 1의 개수를 전부 계산한다.
2. 각 열에 있는 1을 배치하면서 현재 행에 홀수 행이 몇 개 있을 수 있는 상태인지 저장할 배열을 만든다.
3. 현재 가지고 있는 홀수행의 개수를 이용해 다음 열에 있는 1을 배치할 경우, 홀수행을 몇 개 가지고 있는지 계산한다.
4. 위 과정을 모든 열까지 반복하고 최종 열에서 홀수행의 개수가 0인 경우의 수가 몇개인지 return한다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int Mod=10000000+19;

int solution(vector<vector<int>> a) {
    int row=a.size(); //행
    int col=a[0].size(); //열
    vector<vector<int>> nCr(row+1,vector<int>(row+1,0));
    // nCr계산 [n][r]
    for (int i=0; i<=row; i++)
    {
        nCr[i][i]=1;
        nCr[i][0]=1;
    }
    for (int i=2; i<=row; i++)
    {
        for (int j=1; j<row; j++)
        {
            nCr[i][j]=(nCr[i-1][j-1]+nCr[i-1][j])%Mod;
        }
    }
    vector<long long> Cnt(col,0);
    for (int i=0; i<row; i++)
    {
        for (int j=0; j<col; j++)
        {
            Cnt[j]+=a[i][j];
        }
    }
    vector<vector<long long>>DP(row+1,vector<long long>(col,0));
    DP[Cnt[0]][0]=nCr[row][Cnt[0]]; // 첫번째 열에 있는 수들을 배치하면 홀수인 행이 몇개 생기는지
    for (long long x=0; x<col-1; x++)
    {
        for (long long y=0; y<=row; y++)
        {
            for (long long i=0; i<=min(y,Cnt[x+1]); i++)
            {
                // 최대 y개 미만의 홀수를 변경 
                long long evenChange=Cnt[x+1]-i; // 짝수 변경량
                // i개의 홀수 변경 = y-i
                // evenChange만큼 짝수 변경 (row-y) >= evenChange 일때만 변경 가능;
                if (row-y>=evenChange)
                {   
                    DP[y-i+evenChange][x+1]+=((DP[y][x]*nCr[y][i])%Mod*nCr[row-y][evenChange])%Mod;
                }
            }
        }
    }
    return DP[0][col-1];
}

 

---

 

처음에 규칙을 찾는다고 계속 생각했다... 모든 행에 포함된 1이 짝수개가 아닌 경우는 단순히 조합의 곱셈이기 때문에 짝수개인 경우도 조합으로 나타낼 수 있을 것이라고 생각했는데, 아무리 고민해도 아이디어가 떠오르지 않았다.

짝수와 홀수라는 힌트를 봐서 풀 수 있었는데, 만약 못 봤다면 얼마나 고민을 해야 이 문제를 풀 수 있었을까...

 

 

프로그래머스