상어 초등학교 21608

문제

생략

접근 방법

'문제에서 요구한 바를 그대로 해도 해결할 수 있을까?'를 생각해 보자.
가로 세로가 N인 정사각형에서 학생의 수가 N*N인데 학생마다 좋아하는 학생이 4명 있다. 그것을 가까운 4방향으로 확인해 본다면 어떻게 될까?

가로, 세로, 학생의 수를 다 곱하면 N^4
4방향을 확인하며 좋아하는 학생 4명 중 하나인지 확인하는 것 4^2
N은 최악의 경우 20이므로 20^4*4^2=2,560,000
널널한 시간임을 확인할 수 있다.

즉 요구한 대로 구현해 주면 해결되는 문제이다.

코드

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int N, sum = 0;
    cin >> N;
    vector<vector<int>> map(N, vector<int>(N)), input(N * N + 1, vector<int>(4));
    int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1}, score[] = {0, 1, 10, 100, 1000};
    for (int i = 0; i < N * N; ++i)
    {
        int cur;
        cin >> cur;
        for (int j = 0; j < 4; ++j)
            cin >> input[cur][j];
        int cnt = 0, empty = 0, curX = 21, curY = 21;
        for (int y = 0; y < N; ++y)
            for (int x = 0; x < N; ++x)
            {
                if (map[y][x])
                    continue;
                int tempC = 0, tempE = 0;
                for (int j = 0; j < 4; ++j)
                {
                    int ny = y + dy[j], nx = x + dx[j];
                    if (ny < 0 || nx < 0 || ny >= N || nx >= N)
                        continue;
                    for (int k = 0; k < 4; ++k)
                        if (map[ny][nx] == input[cur][k])
                        {
                            ++tempC;
                            break;
                        }
                    if (!map[ny][nx])
                        ++tempE;
                }
                if (tempC > cnt)
                {
                    cnt = tempC;
                    empty = tempE;
                    curX = x;
                    curY = y;
                }
                else if (tempC == cnt && tempE > empty)
                {
                    empty = tempE;
                    curX = x;
                    curY = y;
                }
                else if (tempC == cnt && tempE == empty)
                {
                    if (curY > y)
                    {
                        curX = x;
                        curY = y;
                    }
                    else if (curY == y && curX > x)
                        curX = x;
                }
            }
        map[curY][curX] = cur;
    }
    for (int y = 0; y < N; ++y)
        for (int x = 0; x < N; ++x)
        {
            int cur = map[y][x], cnt = 0;
            for (int i = 0; i < 4; ++i)
            {
                int ny = y + dy[i], nx = x + dx[i];
                if (ny < 0 || nx < 0 || ny >= N || nx >= N)
                    continue;
                for (int j = 0; j < 4; ++j)
                    if (map[ny][nx] == input[cur][j])
                    {
                        ++cnt;
                        break;
                    }
            }
            sum += score[cnt];
        }
    cout << sum;
    return 0;
}

풀이

주의해야 할 점은 문제에서 요구한 3가지를 전부 그대로 해줘야 한다는 것이다.

3번 조건은 1, 2번을 해결하면 자동으로 될 것 같아서 추가 안 했었다가 틀렸다.
내가 주변에 좋아하는 학생이 없고 비어있는 칸이 없는 자리만 남았을 경우도 존재할 수 있기 때문이다.

즉 1~3번 조건을 제대로 이행하면 풀 수 있는 문제이다.