[ 프로그래머스 [ 월간코드챌린지 ] 짝수 행 세기 ] (C++)

프로그래머스의 짝수 행 세기(월간코드챌린지) 문제이다.

[ 문제풀이 ]

풀이 과정이 너무나도 어려운 문제였다.

며칠을 고민했지만, 혼자서 해결하기 너무 힘들어서 다른 분들의 생각을 조금 참고해서 해결하였다.

그럼 지금부터 문제에서 제시한 조건 및 문제풀이에 베이스가 되는 과정들부터 풀이과정 및 정답도출까지 진행해보자.

#1. 제시된 조건

문제에서 제시되어 있는 조건을 다시한번 살펴보자.

조건은 "주어진 2차원 배열 A와 똑같은 크기를 가지는 배열 B를 만들건데, 이 때, B배열의 각 행에 들어있는 1의 갯수가 짝수여야 한다." 라는 것이다. 실제 문제에서는 여러가지 조건들이 더 있지만, 가장 핵심적인 조건은 위의 조건이라고 생각한다. 우리가 구해야 하는 것은, 이 때, 배열 B를 만들 수 있는 경우의 수를 모두 구해야 하는 것이다.

그러면 지금부터 우리가 사용할 단어에 대해서 미리 하나 알고 가자.

지금부터는 "행에 1이 0개이거나 짝수개가 있는 행" 을 "짝수행" 이라고 표현하고, "행에 1이 홀수개가 있는 행"을 "홀수행" 이라고 표현하겠다.

그리고 우리가 구해야 하는 모든 경우의 기준은 "짝수행"이 된다. 홀수행은 짝수행을 구하기 위한 수단 중 하나로만 사용할 것이다.

#2. 경우의 수 구하기

지금부터 할 내용에서는 경우의 수에 대한 이야기가 굉장히 많이 나올 것이다. 왜냐하면 우리가 실질적으로 구해야 하는 값도 경우의 수이기도 하지만, 그 과정에서 "A번열에 '1'이 x개가 있고, B번열에 '1'이 y개가 있을 때 짝수행이 될 수 있는 경우의 수" 혹은 "주어진 행의 크기가 R이고 해당 열에 '1'의 갯수가 x개 일 때, 해당 열에서 짝수행이 될 수 있는 경우의 수" 뭐 이런 계산을 계속해서 해 주어야 한다. 뭐 위에 예시를 이해할 필요도 없고 이해하려고 노력할 필요도 없다. 무튼, 지금 문제를 풀기전에 우리에게 필요한 것이 조합에 대한 경우의 수라는 것이다.

수학적 기호로 나타냈을 때 보통, nCr 로 적는 조합의 경우의 수를 구하는 이 과정을 굉장히 많이 진행하게 된다.

따라서, 먼저 이 경우의 수를 모두 구해놓는 과정부터 알아보자. 지금부터는 nCr을 조금 더 보기좋게 C(n , r) 이라고 표현하겠다. C(n , r)은 다음과 같이 계산이 가능하다. n! / (r! (n - r)!) 로

그런데, 파스칼의 법칙에 의해서 조금 더 간단하게 계산이 가능하다.

C(n , r) + C(n , r + 1) = C(n + 1 , r + 1) 이 점화식이 파스칼의 법칙인데, 이를 C(n , r)을 구하는 식으로 변형을 시켜보면

C(n , r) = C(n - 1 , r - 1) + C(n - 1 , r) 로 구할 수가 있다.

따라서, 우리는 이를 식으로 C(? , ?) 의 값을 모두 구해줄 것이다.

본격적인 문제 풀이에 들어갔을 때, C(n , r)을 사용하는 경우는 이런 경우에서 사용된다.

"하나의 열에 존재하는 '1'의 갯수를 통해서 몇 개의 행을 짝수행으로 만들 수 있을까?" 라는 부분에 대해서 많이 사용된다.

그럼, 지금부터 또 하나 사용할 단어를 정해주자.

주어진 행렬의 행의 크기 = Row, 열의 크기 = Col 이라고 표현하겠다.

하나의 열에는 Row개의 행이 존재할 것이다. 그리고, 각 열마다 주어지는 '1'의 갯수는 당연히 주어지는 Case마다 다를 것이다.

따라서, 우리는 Row개 중에서 '1'을 뽑는 과정, 혹은 '0'을 뽑는 과정을 C(Row , ?) 로 구해줄 것이다.

다시한번 정리해서 말해보면, "Row개에서, 1을 뽑을 수 있는 경우의 수" 혹은 "Row개에서, 0을 뽑을 수 있는 경우의 수"를 구해야 한다. 따라서, 최악의 경우 하나의 열에 1이 Row개 만큼 존재할 수 있기 때문에 우리는 C(1 , 0)부터 C(Row, Row)까지를 구해주어야 한다.

그리고 이 부분에서도 C(n , r)을 n! / (r! (n - r)!) 로 계산할 경우, 최악의 경우 Row = 300이 되기 때문에, 300!이 되는 값을 직접 계산하게 되면 너무나도 많은 연산을 진행해야 하기 때문에 '파스칼의 법칙'을 이용해서 조금 더 빠르고 수월하게 구해주는 것이다.

C(n , r) = C(n - 1 , r - 1) + C(n - 1 , r) 라는 점화식을 통해서 C(1 , 0) ~ C(Row , Row) 까지의 값을 계산해주자.

(이 부분에 대한 구체적인 풀이는 다음 글을 읽으시면 도움이 되실 수도 있습니다.)

[ 백준(11051) 이항계수2 - 풀이 바로가기 ]

#3. 1의 갯수 구하기

각 열에 존재하는 1의 갯수를 미리 구해주자.

1의 갯수로 문제를 해결해야 하기 때문에, 미리 "각 열에 존재하는 1의 갯수"를 구하고 저장해주자.

그리고 지금부터, Arr_OneCnt[] 라는 수식을 사용할 것인데, 말 그대로 1의 갯수를 저장해 놓은 배열을 의미한다.

Arr_OneCnt[0] = 2 라는 것은 "0번 열에는 '1'이 2개가 있습니다." 를 의미한다.

그럼 지금까지 한 내용을 정리를 한번 해보자.

1. 1이 짝수개가 있는 행을 "짝수행", 1이 홀수개가 있는 행을 "홀수행" 이라고 표현하자.

2. C(n , r) = C(n - 1 , r - 1) + C(n - 1 , r) 이라는 점화식을 통해서 C(1 , 0) ~ C(Row , Row) 까지의

   값을 계산하자.

3. Arr_OneCnt[]라는 배열에, "각 열에 존재하는 1의 갯수를 Count"해서 저장해주자.

위에서 선언한 수식들은 밑에서도 굉장히 많이 사용되니 어느정도 충분히 인지를 하고 계속 읽는 것을 권장한다.

#4. 수식 선언 및 초기값 설정.

지금부터 하나의 수식을 선언해보자.

F[A][B] = C 라는 수식을 사용할 것이다. (본문내용 : DP[][])

F[A][B] = C 는, "1열부터 A열까지 계산 했을 때, B개의 짝수행을 가진 배열은 총 C가지가 있습니다." 를 의미한다.

(실제 코드에서 배열은 0열 ~ Col - 1 열까지 존재하지만, 이 설명하는 글에서는 편의상 1열 ~ Col열까지 존재한다고 표현하겠습니다.)

즉, 우리가 1열 ~ Col열까지 순차적으로 진행하면서 모든 값을 제대로 채웠다면, 우리가 원하는 정답은 F[Col][Row] 에 저장되어 있을 것이다.

F[Col][Row] 이 갖는 의미를 풀어서 설명하면, "1열부터 Col열까지 계산했을 때, Row개의 짝수행을 가진 배열의 수" 를 의미한다. 위에서도 말했듯이 우리가 계산하고자 하는 배열의 행의 크기 = Row, 열의 크기 = Col 이기 때문에, F[Col][Row] 가 정답이 될 것이다.

그럼, 1열은 어떻게 될까 ?? 1열은 아마 자체적으로 계산을 해줘야 할 것이다. 왜냐하면 영향을 받을 수 있는 이전에 계산된 열이 존재하지 않기 때문이다. 그럼 계산을 해보자. 우리는 현재 '1열'을 계산하고 있으니, F[A][B] = C에서 A = 1이라는 것을 알 수 있다. 그럼, F[1][B] = C를 계산해야 하는데, 여기서 B와 C에 들어갈 값을 한번 구해보자.

다시한번 수식 'F[1][B] = C'의 의미에 대해서 생각해보자.

"1열부터 1열까지 계산했을 때, B개의 짝수행을 가진 배열은 총 C가지가 있습니다." 이다.

그럼, 1열만 봤을 때, 특정 행이 짝수행이 되기 위해서는 어떻게 배치가 되어야 할까 ??

바로, "반드시 0이 있어야만 짝수행이 될 수 있다" 라는 것이다. 왜냐하면 우리는 이전에 나온 열 없이, 첫 번째 열을 계산하고 있는데, 해당 열에서 '1'이 나와버렸다? 라는 것은 '1'의 갯수가 홀수개가 있다라는 것이고 이는 홀수행이 되버린다는 것이다.

그럼 짝수행이 몇개가 나올 수 있을까 ?? 바로 "0의 갯수" 만큼 짝수행이 나올 수가 있다.

.

맵이 위와 같이 주어졌다고 생각해보자. 1열에서 발생할 수 있는 짝수행의 갯수는 ? 3개이다. 저 1과 0을 어떻게 조합하든지 짝수행은 반드시 3개밖에 존재할 수가 없다.

그럼 그 경우의 수는 몇개가 될까 ?? 위의 그림에서 1열만 가져와서 발생 가능한 모든 경우를 나열해보면 다음과 같은 경우들이 가능하다.

위와 같이 10가지가 가능하다. 그럼 10가지를 어떻게 구할 수 있을까 ??? 이런 경우를 생각해서 우리는 #2에서 조합을 모두 구해놨다. 위의 예시에서는 행의 크기인 5개 에서, 0의 갯수인 3개를 뽑는 경우의 수, 즉, C(5 , 3)을 통해서 10이라는 것을 바로 구할 수가 있다.

그럼 우리가 지금 하고 있는 행의 크기가 Row이고, 1의 갯수가 Arr_OneCnt[1] 인 상황에서는 ??

바로, C(Row , Row - Arr_OneCnt[1]) 가 되는 것이다.

Row - Arr_OneCnt[0] 라는 것은, 행의 크기에서 해당 열에있는 1의 갯수를 빼는 것이니, 즉, 해당 열에있는 0의 갯수를 의미한다. 따라서, F[1][Row - Arr_OneCnt[1]] = C(Row , Row - Arr_OneCnt[0]) 가 되는 것이다.

F[1][Row - Arr_OneCnt[1]] 의 의미를 다시한번 설명하자면,

"1열에서 1열까지 왔을 때, Row - Arr_OneCnt[1] 개의 짝수행을 가질 수 있는 배열은 행의 길이인 Row개 중에서, 1열이 가지고 있는 0의 갯수만큼을 뽑는 경우의 수가 됩니다." 이다.

#5. 문제풀이 및 정답도출

그럼 이제 1열이 아닌 모든 열에 대해서 짝수행의 갯수를 모두 구해보자.

지금부터 조금 편하게 이야기하기 위해서 'A번 열'이라는 배열의 중간에 존재하는 어떤 한 열에 대해서 이야기를 해보자.

그럼, 아마 지금까지 "1열부터 A - 1열까지, 짝수행을 B개 가질 수 있는 경우의 수" 가 계산되어 있을 것이다.

그리고 우리는 A번열에 있는 숫자 '1'들을 이용해서 새로운 행을 만들고 더 나아가 새로운 배열을 만들 것이다.

우리의 기준은 항상 "짝수행" 이다. 그럼 기존의 짝수행들 중에서 'K개의 행'에 '1'을 추가하는 상황을 생각해보자.

'K개의 행에 1을 추가' 한다고 했으니, K의 범위는 0 <= K <= Arr_OneCnt[A] 가 될 것이다.

왜냐하면, A번 열에는 '1'을 Arr_OneCnt[A]개 가지고 있기 때문이다.

다시 말해서, A번 열이 가지고 있는 '1'들 중에서, K개를 기존의 짝수행에 추가시킬 것이고, 그 나머지를 기존의 홀수행에 추가시킬 것이다. 보다 정확하게 말하자면, A번 열이 가지고 있는 '1'들 중에서, K개를 기존의 짝수행에 추가시킬 것이고, 그 나머지인 Arr_OneCnt[A] - K 개의 '1'들을 홀수행에 추가시킬 것이다.

그럼 이렇게 되었을 때의 상황을 한번 생각을 해보자.

기존의 짝수행이었던 행에 '1'을 추가하게 되면 어떻게 될까 ?? 이 행은 홀수행이 될 것이다.

기존의 홀수행이었던 행에 '1'을 추가하게 되면 어떻게 될까 ?? 이 행은 짝수행이 될 것이다.

크게는 위와 같이 2가지 상황이 존재한다.

그런데, 이런경우가 있을 수 있다.

기존의 짝수행이 총 3개가 있었는데, 현재 내가 '1'을 추가하고자 하는 행의 갯수가, 즉, K의 값이 2인 경우를 생각해보자.

짝수행이 3개가 있었고, 나는 A번 열에 있는 '1'들 중 2개를 뽑아서 기존의 짝수행에 추가시킬 것이다.

그럼 ?? 짝수행 3개중 2개는 홀수행이 되겠지만, 기존의 짝수행 중 1개는 그대로 짝수행으로 남을 것이다.

왜 ? 1을 추가하지 않기 때문이다.

즉, A번 열에서 기존의 짝수행 중, K개의 행에 '1'을 추가함으로써 짝수행이 될 수 있는 경우와 그 갯수는 다음과 같다.

1. 기존의 짝수행들 중, K개의 선택을 받지 못해서, 짝수행 그대로 남아있는 경우

2. 기존의 홀수행들 중, '1'들을 추가함으로써, 짝수행이 되는 경우

1번의 경우, 짝수행이지만 K개의 선택을 받지 못한 나머지 행을 의미하므로 "기존의 짝수행의 갯수 - K개의 짝수행이 발생" 하게 된다.

2번의 경우 그 갯수는 짝수행에 추가되는 K개의 1들을 제외한, Arr_OneCnt[A] - K 개의 '1'들이 추가되는 것이므로

"Arr_OneCnt[A] - K개의 짝수행이 발생". 하게 된다.

즉, 결과적으로 나타내보면 A번열에서 발생할 수 있는 짝수행의 갯수는

"(기존의 짝수행의 갯수 - K) + (Arr_OneCnt[A] - K)" 개가 된다. 이 식을 정리해보면...

"기존의 짝수행의 갯수 + Arr_OneCnt[A] - (2 * K)" 가 된다. 식이 길기 때문에 지금부터 이 식을 "Be_Even_Num" 이라고 표현하겠다. 의미는 "짝수행이 될 행의 갯수" 를 의미한다.

그런데 우리가 여기서 알아야 할 정보가 하나 더 생겼다.

바로, "기존의 짝수행의 갯수"이다. 본인은 이 부분을 간단하게 0개 ~ Row개 까지 모두 탐색을 해주었다.

짝수행이 될 수 있는 갯수는 0개부터 Row개까지 가능하기 때문이다. 간단하게 "기존의 짝수행의 갯수" 를 'Even_Num' 개 라고 표현하겠다.

그럼 여기까지의 내용을 한번 정리하고 경우의 수를 구해보자.

1. 우리는 현재 탐색하고 있는 A열에서 K개의 '1'을 기존의 짝수행에 추가할 것이다.

2. K개의 '1'을 제외한 나머지 '1'들을 홀수행에 추가할 것이다.

3. 이 과정에서, 발생할 수 있는 짝수행은 다음과 같이 2가지 경우가 존재한다.

   1. 기존의 홀수행 + '1'을 추가

   2. 기존의 짝수행 + '1'을 추가하지 못함.

4. 3번을 통해서 우리는 "Be_Even_Num" 을 구해주었다.

그럼 이제 경우의 수를 구해보자.

위의 1번과정에서 우리는 '기존의 짝수행 중에서 K개를 선택하는 과정' 이 필요하다.

즉, C(Even_Num , K) 를 계산해 주어야 한다.

2번 과정에서 '기존의 홀수행 중에서 K개의 1을 제외한 나머지 1을 선택하는 과정' 이 필요하다.

즉, C(Row - Even_Num , Arr_OneCnt[A] - K) 를 계산해 주어야 한다.

이 식에서 Row - Even_Num은 "행의 크기에서 기존의 짝수행의 갯수를 빼주는 연산이므로, 기존의 홀수행의 갯수"를 의미한다.

Arr_OneCnt[A] - K는 "A열이 가진 '1'의 갯수에서 짝수행에 들어가는 K개의 '1'을 뺀 나머지 '1'의 갯수"를 의미한다.

즉, A번열에서 짝수행이 될 수 있는 행의 갯수 = C(Even_Num , K) * C(Row - Even_Num , Arr_OneCnt[A] - K) 를 의미한다.

이를 수식으로 나타내보면

F[A][Be_Even_Num] =

C(Even_Num , K) * C(Row - Even_Num , Arr_OneCnt[A] - K) * F[A - 1][Even_Num] 이 된다.

우리가 구하고자 하는 것이 경우의 수이니, 기존의 짝수행의 갯수에 따라 발생 가능한 배열의 갯수 만큼을 또 곱해주어야 하기 떄문에 식의 가장 마지막에 F[A - 1][Even_Num] 이 곱해진 것이다.

물론, 다음과 같은 경우는 계산 없이 그냥 건너뛰어도 되는 상황이다.

1. 기존의 짝수행으로 발생할 수 있는 배열의 수가 0개인 경우.

위에서 본인은 기존의 짝수행의 갯수를 0개 ~ Row개까지 모두 탐색해 주었다고 했다.

그런데, F[A - 1][탐색한 짝수행의 갯수] = 0 인 경우를 생각해보자.

이는, 이전 열까지 계산했을 때, 해당 짝수행을 가지고 있는 배열이 존재하지 않는다는 것을 의미하고, 우리가 위에서 진행했던

계산이 필요가 없는 경우이다.

2. 기존의 짝수행의 갯수가 K보다 작은 경우.

우리는 현재 열에서 K개의 '1'을 기존의 짝수행에 추가하는 연산을 진행했었다.

그런데, 내가 짝수행에 추가하려는 '1'의 갯수가 3개라고 가정해보자. 즉 K = 3인상황이다.

이 상황인데, 기존의 짝수행의 갯수가 2개라고 생각해보자.

그럼, 2개중에서 3개를 선택하는 모순적인 상황이 발생한다. 이 경우 또한 계산을 해주지 않아도 된다.

마지막으로 코드로 정리해보자.

    vector<vector<long long>> DP(Col + 2, vector<long long>(Row + 1, 0));
    DP[1][Row - Arr_OneCnt[0]] = nCr[Row][Row - Arr_OneCnt[0]];
 
    for (int Column = 1; Column < Col; Column++)
    {
        int OneCnt = Arr_OneCnt[Column];
        for (int Even_Num = 0; Even_Num <= Row; Even_Num++)    
        {
            if (DP[Column][Even_Num] == 0) continue;
            for (int K = 0; K <= OneCnt; K++)
            {
                if (Even_Num < K) continue;
 
                int Be_Even_Row = Even_Num + OneCnt - (2 * K);
                if (Be_Even_Row > Row) continue;
 
                long long Result = (nCr[Even_Num][K] * nCr[Row - Even_Num][OneCnt - K]) % MODULER;
                DP[Column + 1][Be_Even_Row] = (DP[Column + 1][Be_Even_Row] + DP[Column][Even_Num] * Result);
                DP[Column + 1][Be_Even_Row] %= MODULER;
            }
        }
    }

본인이 #5부분을 코드로 구현한 것이다.

line2)에서 보면 #4에서 진행했던 초기값 설정을 하는 부분이다.

line4)가 전체 열을 탐색하는 과정이다. 1열 ~ Col열까지 탐색을 하는 과정이다.

이 때 탐색의 범위는 1 ~ Col - 1 까지 진행했지만, 실제로 값을 저장하는 부분인 line18, 19를 보게되면 Column + 1번 Index에다가 저장을 해 주었다.

즉, 쉽게 이야기해서 우리가 위에서 이야기 한 것과 같이 0번열 ~ Col - 1열까지 값을 설정한 것이 아닌,

1번열 ~ Col번열 까지 값을 설정해 주었다.

line7)은 "기존 열까지 발생할 수 있는 짝수행의 갯수를 모두 탐색하는 과정" 이다.

발생할 수 있는 짝수행의 갯수는 0개 ~ Row개가 된다.

하지만, 위에서 언급했듯이 계산을 하지 않아도 되는 경우가 있다.

line9)처럼, "이전 열까지 Even_Num개의 짝수행을 만들 수 있는 배열이 없는 경우" 는 계산을 할 필요가 없다.

line10)은 "짝수행에 추가하고자 하는 '1'의 갯수"를 설정하는 부분이다.

마찬가지로 계산을 하지 않아도 되는 경우가 있다.

line11) 처럼, "이전 열까지 계산했을 때, 만들어진 짝수행의 갯수" 보다 "짝수행에 추가하고자 하는 '1'의 갯수"가 더 큰 경우,

즉, 기존의 짝수행은 2개밖에 없는데, 나는 3개의 짝수행에 '1'을 추가하고 싶어하는 이런 경우는 계산에 모순이 되는 부분들이다.

line14)는 우리가 위에서 구했던 "Be_Even_Row"의 값, 즉, "짝수행이 될 수 있는 행의 갯수"를 계산해주는 부분이다.

line17)은 위에서 구했던 값들을 통해서 발생 가능한 경우의 수를 구하는 부분이다.

line18)은 발생 가능한 경우의 수를 저장해 주는 부분이다.

[ 소스코드 ]

#include <vector>
 
#define MODULER 10000019
using namespace std;
 
void Calculate_Combination(vector<vector<long long>> &V, int Row)
{
    V[0][0] = 1;
    for (int i = 1; i <= Row; i++)
    {
        for (int j = 0; j <= Row; j++)
        {
            if (j == 0) V[i][j] = 1;
            else if (i == j) V[i][j] = 1;
            else V[i][j] = V[i - 1][j - 1] + V[i - 1][j];
 
            V[i][j] %= MODULER;
        }
    }
}
 
void Calculate_OneCnt(vector<int> &V, vector<vector<int>> MAP)
{
    for (int i = 0; i < MAP.size(); i++)
    {
        for (int j = 0; j < MAP[0].size(); j++)
        {
            V[j] += MAP[i][j];
        }
    }
}
 
int solution(vector<vector<int>> a) 
{
    int Row = a.size();
    int Col = a[0].size();
    
    vector<vector<long long>> nCr(Row + 1, vector<long long>(Row + 1, 0));
    Calculate_Combination(nCr, Row);
 
    vector<int> Arr_OneCnt(Col + 1, 0);
    Calculate_OneCnt(Arr_OneCnt, a);
 
    vector<vector<long long>> DP(Col + 2, vector<long long>(Row + 1, 0));
    DP[1][Row - Arr_OneCnt[0]] = nCr[Row][Row - Arr_OneCnt[0]];
 
    for (int Column = 1; Column < Col; Column++)
    {
        int OneCnt = Arr_OneCnt[Column];
        for (int Even_Num = 0; Even_Num <= Row; Even_Num++)    
        {
            if (DP[Column][Even_Num] == 0) continue;
            for (int K = 0; K <= OneCnt; K++)
            {
                if (Even_Num < K) continue;
 
                int Be_Even_Row = Even_Num + OneCnt - (2 * K);
                if (Be_Even_Row > Row) continue;
 
                long long Result = (nCr[Even_Num][K] * nCr[Row - Even_Num][OneCnt - K]) % MODULER;
                DP[Column + 1][Be_Even_Row] = (DP[Column + 1][Be_Even_Row] + DP[Column][Even_Num] * Result);
                DP[Column + 1][Be_Even_Row] %= MODULER;
            }
        }
    }
    return DP[Col][Row];
}