백준 g1 17143 낚시왕 c++

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

17143번: 낚시왕

 

문제 설명

1. 낚시왕 오른쪽 한 칸 이동
2. 같은 열 중 가장 가까운 상어 잡음
3. 상어 이동
   1. 칸 넘으면 반대 방향
   2. 한 칸에 여러 상어 -> 가장 큰 상어만 살아남음

문제 풀이

중요한 것은 상어의 이동이다

1. 상어들이 벽 끝에 부딪혔을 때를 어떻게 한번에 계산해서 다음 위치를 정할 지

2. 상어를 옮기면서 먹으면, 이동해서 다른 곳에 가있어야 할 상어가 먹히는 경우가 있음.

ex. 상어 4 와 상어 1이 있을 때, 상어 1 다음에 상어 4가 움직여야함. 근데 상어 1이 먼저 움직여서 상어 4 위치로 가버렸을 때, 상어 4는 원래 다른 곳으로 이동할 예정이었으므로 먹히면 안 됨

 

1. 상어의 이동

 

상어의 위치는 1, 1부터 시작

• 나는 현재 위치 i부터 해당 방향으로의 벽 까지 거리를 먼저 구한 후, 
  • 상 방향이라면 i - 1, 하 방향이라면 N - i
• if 만약 구한 거리가 속력(가야 할 거리, dist)보다 작다면, 그냥 이동한다. 
  • 상 방향이라면 nx = i - dist, 하 방향이라면 nx = i + dist
• else if 만약 구한 거리가 속력(가야 할 거리)와 같다면, 그냥 이동하되 방향을 반대로 바꿔준다.
• else 만약 구한 거리가 속력보다 크다면, 먼저 벽 까지 이동을 하고, (i-1 or N-i), (N-1)개가 반복 되므로 N-1로 나눠준다. 몫이 짝수냐 홀수냐에 따라 끄트머리의 방향이 다른데, 그 방향대로 나머지를 더해주면 된다.
  • 가야 할 거리 dist = (i-1) + (N-1) * 몫 + 나머지
    • 여기서 첫 항은 벽까지 이동하는 거리, 둘째 항은 반복되는 구간, 셋째 항은 남은 끄트머리를 방향에 따라 1이나 N에서 시작해서 더해주면 된다. 
    •  

< 상 방향 일때 >

if (dist < i - 1) { // 가야 할 거리가 벽까지의 거리보다 작을 때는 그냥 i에서 dist만큼 위로 이동
    nx = i - dist;
    // 방향 그대로
} else if (dist == i - 1) { // 가야 할 거리 == 벽까지의 거리면 벽 앞에 도착하므로, 방향 반대
    nx = i - dist;
    shark[s][1] = 2; // 방향 하
} else { // 가야 할 거리가 벽까지의 거리보다 클 때
    int quotient = (dist - (i - 1)) / (N - 1); // 먼저 벽까지 이동한 후, N-1로 나눠서
    int reminder = (dist - (i - 1)) % (N - 1); // 반복되는 구간과 나머지를 구한다.

    if (quotient % 2 == 0) { // 만약 반복되는 구간이 짝수면 벽 앞인 1에서 시작, 방향은 하
        nx = 1 + reminder;
        shark[s][1] = 2; // 방향 하
    } else { // 만약 반복되는 구간이 짝수면 밑에서부터 시작
        nx = N - reminder;
        shark[s][1] = 1; // 방향 상
    }
}

 

 

2. 상어를 옮기면서 먹으면, 이동해서 다른 곳에 가있어야 할 상어가 먹히는 경우가 있음.

 

이 경우는 상어를 s=1번 ~ s=S번까지 차례대로 for문을 돌리기 때문에,

만약 위치가 겹치는 상어가 내 번호보다 크다면, 곧 움직일 예정이므로 먹지 않고 board에 내 번호를 표시한다.

만약 내 번호보다 작다면 이미 움직인 상어고, 나랑 위치가 겹치기 때문에 더 큰 상어가 살아남는다.

if (board[i][j] == s) {
            // 내가 있던 자리였으면 0, 다른 애가 있는 자리면 그대로 놔둬야 함
            board[i][j] = 0;
        }

        if (board[nx][ny] != 0 && board[nx][ny] < s) {
            // 이미 자리가 있고, 그게 나보다 이전에 이동한 상어라면 먹어야함
            int other = board[nx][ny];

            if (shark[s][2] > shark[other][2]) {
                board[nx][ny] = s;
                shark[s][3] = nx;
                shark[s][4] = ny;
                isDead[other] = true;
            } else {
                board[nx][ny] = other;
                isDead[s] = true;
            }
        } else {
            board[nx][ny] = s;
            shark[s][3] = nx;
            shark[s][4] = ny;
        }

 

 

전체 코드

/*boj g1 17143 낚시왕*/
#include <iostream>
#include <vector>
#define MAXN 105
using namespace std;

int N, M, S;
int board[MAXN][MAXN];
int shark[MAXN * MAXN][5]; // 속력, 이동방향, 크기, x, y 위치
bool isDead[MAXN * MAXN];
// board, 상어 번호 모두 1부터 시작

int dx[5] = {0, -1, 1, 0, 0};
int dy[5] = {0, 0, 0, 1, -1};

int ans = 0;

void print() {
    cout << "\n====================\n";
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cout << board[i][j] << " ";
        }
        cout << "\n";
    }
}

void input() {
    cin >> N >> M >> S;
    for (int i = 1; i <= S; i++) {
        int r, c, s, d, z;
        cin >> r >> c >> s >> d >> z;

        board[r][c] = i;

        shark[i][0] = s;
        shark[i][1] = d;
        shark[i][2] = z;
        shark[i][3] = r;
        shark[i][4] = c;
    }
}

void catchShark(int j) {
    for (int i = 1; i <= N; i++) {
        if (board[i][j] != 0) {
            int s = board[i][j];
            ans += shark[s][2];
            board[i][j] = 0;
            isDead[s] = true;
            break;
        }
    }
}

void moveShark() {
    for (int s = 1; s <= S; s++) {
        if (isDead[s]) continue;

        int i = shark[s][3];
        int j = shark[s][4];

        int dir = shark[s][1];
        int nx = i;
        int ny = j;

        int dist = shark[s][0];

        if (dir == 1) { // 상 이면
            if (dist < i - 1) {
                nx = i - dist;
                // 방향 그대로
            } else if (dist == i - 1) {
                nx = i - dist;
                shark[s][1] = 2; // 방향 하
            } else {
                int quotient = (dist - (i - 1)) / (N - 1);
                int reminder = (dist - (i - 1)) % (N - 1);

                if (quotient % 2 == 0) {
                    nx = 1 + reminder;
                    shark[s][1] = 2; // 방향 하
                } else {
                    nx = N - reminder;
                    shark[s][1] = 1; // 방향 상
                }
            }
        } else if (dir == 2) { // 하 이면
            if (dist < N - i) {
                nx = i + dist;
                // 방향 그대로
            } else if (dist == N - i) {
                nx = i + dist;
                shark[s][1] = 1; // 방향 상
            } else {
                int quotient = (dist - (N - i)) / (N - 1);
                int reminder = (dist - (N - i)) % (N - 1);

                if (quotient % 2 == 0) {
                    nx = N - reminder;
                    shark[s][1] = 1; // 방향 상
                } else {
                    nx = 1 + reminder;
                    shark[s][1] = 2; // 방향 하
                }
            }
        } else if (dir == 3) { // 우 이면
            if (dist < M - j) {
                ny = j + dist;
                // 방향 그대로
            } else if (dist == M - j) {
                ny = j + dist;
                shark[s][1] = 4; // 방향 좌
            } else {
                int quotient = (dist - (M - j)) / (M - 1);
                int reminder = (dist - (M - j)) % (M - 1);

                if (quotient % 2 == 0) {
                    ny = M - reminder;
                    shark[s][1] = 4; // 방향 좌
                } else {
                    ny = 1 + reminder;
                    shark[s][1] = 3; // 방향 우
                }
            }
        } else { // 좌 이면
            if (dist < j - 1) {
                ny = j - dist;
                // 방향 그대로
            } else if (dist == j - 1) {
                ny = j - dist;
                shark[s][1] = 3; // 방향 우
            } else {
                int quotient = (dist - (j - 1)) / (M - 1);
                int reminder = (dist - (j - 1)) % (M - 1);

                if (quotient % 2 == 0) {
                    ny = 1 + reminder;
                    shark[s][1] = 3; // 방향 우
                } else {
                    ny = M - reminder;
                    shark[s][1] = 4; // 방향 좌
                }
            }
        }

        if (board[i][j] == s) {
            // 내가 있던 자리였으면 0, 다른 애가 있는 자리면 그대로 놔둬야 함
            board[i][j] = 0;
        }

        if (board[nx][ny] != 0 && board[nx][ny] < s) {
            // 이미 자리가 있고, 그게 나보다 이전에 이동한 상어라면 먹어야함
            int other = board[nx][ny];

            if (shark[s][2] > shark[other][2]) {
                board[nx][ny] = s;
                shark[s][3] = nx;
                shark[s][4] = ny;
                isDead[other] = true;
            } else {
                board[nx][ny] = other;
                isDead[s] = true;
            }
        } else {
            board[nx][ny] = s;
            shark[s][3] = nx;
            shark[s][4] = ny;
        }
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    input();
    // 1. 낚시왕 오른쪽 한 칸 이동
    for (int king = 1; king <= M; king++) {
        // print();
        //      2. 같은 열에 있는 상어 잡음
        catchShark(king);

        // 3. 상어 이동
        moveShark();
    }

    cout << ans << "\n";
}

 

 

사담

 

상어 이동을 처음엔 하나의 식으로 깔끔하게 정리하려다가 계속 틀려서 결국 포기했다.

공식을 깔끔하게 세울 수 있는 건, 어떻게 끼워맞추는 게 아니라 그 과정들이 모두 정당하고 근거가 있어야 한다는 것 ...

그렇지 않고서야 반드시 틀린 테스트케이스가 나올 수 밖에 없다

될 거 같은데 ?? 하고 어쩌다 맞히는 걸 기대하지 말고 그냥 문제 따라서 풀자

 

공식은 그 이후에 가정들이 뒷받침 되어야만 세울 수 있음