[SW Expert Academy] 코드 배틀!

이번주 화요일에도 코드 배틀이 있었습니다!

[Battle 23] 장마 기간에는 쾌적한 실내에서 코드 배틀!

이었군요..

역시! 비 오는날에도 쾌적하게 즐길 수 있는 갓갓 알고리즘!!! 오늘도 한번 풀어보겠습니다!

SW Expert Academy의 문제는 저작권이 있기 때문에 링크로 대체하겠습니다!

문제 제목을 클릭하면 해당 문제로 이동합니다으아

4615. 재미있는 오셀로 게임

큰 알고리즘이 필요 없는 간단한 구현 문제입니다!

돌이 놓여진 좌표에서 대각선, 위, 아래, 왼쪽, 오른쪽 팔방향에서 돌이 어떻게 바뀌는지만 구현하면 됩니다!

돌이 놓여지다가 같은색 돌을 만나게되면, 그 사이에 있는 돌들을 자신의 돌로 바꾸고 바꾼 갯수만큼 해당 돌의 수를 올려주면 됩니다!

또한, 돌을 놓았기 때문에 놓아진 돌의 수 1개도 함께 증가시켜야겠죠!

이것들만 유의하면서 구현하면 큰 탈 없이 문제를 풀 수 있습니다!

그림으로 알아보겠습니다!

상대의 돌이 바뀌는 경우입니다! 양 끝에 자신의 돌이 놓여있어야 합니다.

만약, 자신의 돌이 양 끝에 없다면 아무일도 일어나지 않습니다.

코드

#pragma once
#include<cstdio>
#include<cstring>
 
int n, m;
int map[10][10];
enum COLOR {WH = 2, BL = 1};
int nums[3];
 
int dy[8] = { -1,-1,-1, 0, 0, 1,1,1 };
int dx[8] = { -1, 0, 1,-1, 1,-1,0,1 };
 
int Q[100][2];
int fr = 0 , re = 0;
 
int getNum(int x, int y, int col)
{
    int ret = 0;
 
    for (int d = 0; d < 8; d++)
    {
        int n = 0;
        int nX = x + dx[d];
        int nY = y + dy[d];
 
        fr = re = 0;
 
        while (map[nY][nX] != col)
        {
            if (map[nY][nX] == 0) break;
            else if (map[nY][nX] == -1) break;
            n++;
            Q[re][0] = nY;
            Q[re++][1] = nX;
            
            nX += dx[d];
            nY += dy[d];
        }
 
        if (map[nY][nX] == col)
        {
            while (re != fr)
            {
                map[Q[fr][0]][Q[fr][1]] = col;
                fr++;
            }
            ret += n;
        }
    }
 
    return ret;
}
 
int main()
{
    int t;
    scanf("%d\n", &t);
 
    memset(map, -1, sizeof(map));
 
    for (int tc = 1; tc <= t; tc++)
    {
        scanf("%d %d\n", &n, &m);
 
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
                map[i][j] = 0;
        }
 
        int x, y, col;
 
        y = x = n / 2;
 
        map[y][x] = WH;
        map[y + 1][x] = BL;
        map[y + 1][x + 1] = WH;
        map[y][x + 1] = BL;
        nums[1] = nums[2] = 2;
 
        while (m--)
        {
            scanf("%d %d %d\n", &y, &x, &col);
            int num = getNum(x, y, col);
 
            map[y][x] = col;
 
            nums[col] += num + 1;
            nums[col ^ 3] -= num;
        }
 
        printf("#%d %d %d\n", tc, nums[BL], nums[WH]);
    }
    return 0;
}

4613. 러시아 국기 같은 깃발

이 문제에서 가장 중요한 것은 바로 행의 구역을 딱 3 개로 나눠서 칠해야 한다는 것이었습니다.

즉, 파란색의 시작과 끝점만 정한다면, 맨처음부터 파란색이 시작되기 전 부분은 하얀색으로 정해지고 파란색이 끝나는 부분부터는 빨간색이라는 것이죠!

이제 부분 합을 이용해서 각 행마다 빨간색으로 바꾸어야 하는 부분과 파란색으로 바꾸어야 하는 부분, 하얀색으로 바꾸어야 하는 부분을 정해주면 됩니다!

이렇게 부분합을 이용해서 각 행마다 변해야하는 색을 정해주면, 파란색이 시작될때의 행과 파란색이 끝날 때의 행을 정해주었을 때, 바뀌어야 하는 부분은 다음과 같이 구할 수 있습니다.

하얀색으로 바꾸어야하는 부분합 = 처음 ~ 파란색 시작 위치 전

 + 파란색으로 바꾸어야하는 부분합 = 파란색 시작 위치 ~ 파란색 끝 위치

 + 빨간색으로 바꾸어야하는 부분합 = 파란색 끝 위치 다음 ~ 끝

참고로, A~B사이의 부분합을 구하기 위해서는

부분합(B, A - 1)을 해야 합니다!

따라서, 부분합의 인덱스는 1부터 시작하게 하고 인덱스 0 에는 0 값을 넣어준다면 무리없이 부분합을 구할 수 있습니다!

코드

 

#pragma once
#include<cstdio>
#include<cstring>
 
char colors[51][51];
int nums[51][4] = { 0 }, n, m;
enum COLOR {WH = 1, BL = 2, RE = 3};
 
int conv[4];
 
int main()
{
    int t;
    scanf("%d\n", &t);
    conv[WH] = 'W';
    conv[RE] = 'R';
    conv[BL] = 'B';
 
    for (int tc = 1; tc <= t; tc++)
    {
        scanf("%d %d\n", &n, &m);
        memset(memoi, 0, sizeof(memoi));
 
        for (int i = 1; i <= n; i++)
        {
            scanf("%s\n", colors[i]);
 
            for(int j = 1; j < 4; j++)
                nums[i][j] = nums[i - 1][j];
 
            for (int j = 0; j < m; j++)
            {
                nums[i][WH] += colors[i][j] != conv[WH];
                nums[i][RE] += colors[i][j] != conv[RE];
                nums[i][BL] += colors[i][j] != conv[BL];
            }
        }
 
        int min = 98764321;
 
        for (int st = 2; st <= n - 1; st++)
        {
            for (int ed = st; ed <= n - 1; ed++)
            {
                int cnt = nums[st - 1][WH] - nums[0][WH];
                cnt += nums[ed][BL] - nums[st - 1][BL];
                cnt += nums[n][RE] - nums[ed][RE];
 
                min = min < cnt ? min : cnt;
            }
        }
 
        printf("#%d %d\n", tc, min);
    }
    return 0;
}
 

아쉽지만, 이번에는 두 문제밖에 못풀었습니다. 개구리 점프가 생각보다 매우 강력하네요...

다음에 한 번 다시 도전해봐야 할 것 같습니다!

뭔가 풀릴듯 말듯 하네요..

코드배틀 결과는!

9등 입니다! 

점점.. 낮아지는 느낌이 있는것 같기도 하네요