[C언어] 백준 1018 : 체스판 다시 칠하기

19822 단어 C백준C

내가 이해한 문제

  • N과 M만큼의 사각형이 있다. 그 사각형에서 가능한 8*8크기의 사각형을 떼어내고, 그 사각형이 흰검이 번갈아서 칠해지지 않는 경우를 모조리 다 센다.

  • 그 수 중 제일 조금만 바꾸어도 되는 경우를 출력한다.

  1. 먼저 반복문을 쓸 생각을 했다.

  2. 가로 * 세로이므로 이차원 배열을 쓸 생각을 했다.

  3. 2번을 토대로 arr[ i ][ j ]를 만들었고, 이 arr는 BW를 집어넣는 공간이다.(사각형 공간)

  4. 번갈아져서 칠해지지 않는 경우를 세기위해, flag를 설정해주었다.

  5. 10x10크기의 사각형이 있다고 가정하자. 이 때 떼어낼 수 있는 사각형의 갯수는 9개다. 그걸 각각 최솟값과 비교해야하기 때문에 count[(n - 3) * (m - 3)]의 배열을 만들어주고, flag를 넣어주었다.

  6. 여기서 문제가 생겼는데, 첫 사각형은 그렇다 쳐도 두번째 사각형을 만들 때 그 위치를 어떻게 지정해야할지 모르겠다..

내가 푼 코드 (틀림)

#include <stdio.h>

int main()
{
    int a, b, c, i, j, k;
    char arr[51][51];
    int n, m, flag;
    scanf("%d %d", &n, &m);
    int count[(n - 7) * (m - 7)];
    a = 0;
    c = 0;
    i = 0;
    while (i < n)
    {
        scanf("%s", &arr[i]);
        i++;
    }
    while (a + 7 != n)
    {
        b = 0;
        {
            while (b + 7 != m)
            {
                i = 0;
                flag = 0;
                while (i < 8)
                {
                    j = 0;
                    while (j < 8)
                    {
                        if ((b + j) % 2 == 0)
                        {
                            if (arr[a + i][b] != arr[i][j])
                            flag++;
                        }
                        else
                        {
                            if (arr[a + i][b] == arr[i][j])
                            flag++;
                        }// 여기서 잘 손보면 될 것 같은데 진짜 모르겠다..
                        j++;
                    }
                    i++;
                }
                count[c] = flag;
                c++;
                b++;
            }
            a++;
        }
    }
    int min;
    min = count[0];
    i = 0;
    while (i < (n - 7) * (m - 7))
    {
        if (count[i] < min)
        {
            min = count[i];
        }
        i++;
    }
    printf("%d", min);
}

다른 사람 풀이

https://mjeong9316.tistory.com/167
이분 꺼 보고 거의 복붙했다..

#include <stdio.h>

#define minFinder(a, b) a < b ? a : b

int main()
{
    int a, b, i, j;
    char arr[51][51];
    int n, m, flagW, flagB, min = 80;
    scanf("%d %d", &n, &m);
    i = 0;
    while (i < n)
    {
        scanf("%s", &arr[i]);
        i++;
    }
    i = 0;
    while (i + 7 < n)
    {
        j = 0;
        while (j + 7 < m)
        {
            flagW = 0;
            flagB = 0;
            a = i;
            while (a < i + 8)
            {
                b = j;
                while (b < j + 8)
                {
                    if ((a + b) % 2 == 0)
                    {
                        if (arr[a][b] == 'B')
                            flagW++;
                        else
                            flagB++;
                    }
                    else
                    {
                        if (arr[a][b] == 'B')
                            flagB++;
                        else
                            flagW++;
                    }
                    b++;
                }
                a++;
            }
            min = minFinder(min, flagB);
            min = minFinder(min, flagW);
            j++;
        }
        i++;
    }
    printf("%d", min);
}

내 코드의 문제점

while (i < 8)
{
    j = 0;
    while (j < 8)
    {

여기서 그냥 8개를 돌려버린 것.. t = i, t1 = j 하고 t < 8 + i, t1 < 8 + j 고려해야 하는건 알고있었지만, 진짜 당시에는 어떻게 해야될지 몰랐다..

또한 flag를 세우는 건 좋았지만, flag1를 따로 잡고 두개중 비교를 해야된다는 생각은 생각조차 못했었다. 자세한 설명은 위 링크에 있다..

큰 방향은 맞아서 다행이지만, 논리를 알아도 코드를 못짜겠다.. 시간이 더 필요한듯 하다

좋은 웹페이지 즐겨찾기