[C/C++] 백준 #2630 색종이 만들기(분할정복)

이번 문제는 분할정복을 이용해서 풀면 어렵지 않게 풀 수 있습니다.

 

color sheets

 

C/C++을 사용하다보면, 반환값을 여러개를 두고 싶은데, 그것이 어렵거나 할 때가 많죠.  색종이 만들기 문제에서는 흰종이와 파란종이를 나누어서 출력을 해주어야 하는데, 그것이 잘 안 되죠.

 

https://www.acmicpc.net/problem/2630

 

반환값을 여러개가 안 되니까, 제 경우에는 65536(\(2^{16}\))의 값을 흰종이로 두고서 4바이트 정수 1개를 가지고 2바이트 정수 2개를 만들어서 사용했습니다.

 

분할정복한 결과가 4개의 구역이 모두 같은 색인 경우에는 1개의 종이로 대치하는 부분을 작성했습니다.

    int s = rec(r, c, v, n);
    s += rec(r+n, c, v, n);
    s += rec(r, c+n, v, n);
    s += rec(r+n, c+n, v, n);
    if((s>>16) == 0) return 1;
    if((s&0xffff) == 0) return 65536;

 

이 코드에서 s에는 4개의 부분에서 얻어진 결과를 흰종이 몇개 파란종이 몇개 형태로 받습니다.  흰종이 갯수가 0개거나 파란종이 갯수가 0개인 경우에는 1개의 파란종이 또는 흰종이라고 바꿉니다.  이 과정을 거치면 분할정복의 정복(conquer) 과정이 마무리가 됩니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2630
//        - by Aubrey Choi
//        - created at 2019-08-02
//------------------------------------------------
#include <stdio.h>

int rec(int r, int c, char v[][128], int n)
{
    if(n==1) return v[r][c]?65536:1;
    n>>=1;
    int s = rec(r, c, v, n);
    s += rec(r+n, c, v, n);
    s += rec(r, c+n, v, n);
    s += rec(r+n, c+n, v, n);
    if((s>>16) == 0) return 1;
    if((s&0xffff) == 0) return 65536;
    return s;
}

int main()
{
    int n, s;
    char v[128][128];
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            scanf("%d", &s);
            v[i][j]=s;
        }
    }
    s = rec(0, 0, v, n);
    printf("%d\n%d\n", s&0xffff, s>>16);
    return 0;
}