[백준] 17143번: 낚시왕 (좌우 반복 이동 구현💡)

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

17143번: 낚시왕

매우매우 유용한 문제였다.

여기서 관건은 물고기의 정보를 어떻게 관리하고, 어떻게 좌우로, 상하로 반복적으로 움직이게 하느냐가 관건이었다.

 

우선 매번 배열에 물고기의 정보를 저장하고 옮기기엔 불편하다.

그래서 물고기마다 번호를 매겨서 별도의 벡터에 물고기의 정보를 저장해두고, 인덱스로 시간복잡도는 $O(1)$로 정보를 바로 파악할 수 있게 했다.

그리고 2차원 배열에는 살아있는 물고기의 번호만을 표시해두어 땅에서 접근하도록 한 뒤, 바로 물고기의 번호를 알 수 있도록 한다.

 

물고기의 이동의 경우 최대 1,000번까지 이동하기 때문에 만약 이를 쌩구현하면 상당한 시간이 소요된다.

그래서 나는 방향마다, 위치마다 패턴으로 횟수마다 이동하지 않고 바로 도착지를 알 수 있도록 했다.

 

// 위
if(d == 0) {
    int left = s - r;
    int turn = left / (R - 1);
    int more = left % (R - 1);
    if(more== 0) {
        if(turn % 2 == 0) {
            nr = 0;
        }
        else {
            nr = R - 1;
            d = 1;
        }
    }
    else {
        if(turn % 2 == 0) {
            nr = more;
            d = 1;
        }
        else {
            nr = R - 1 - more;
        }
    }
}
// 아래
else if(d == 1) {
    int left = s - (R - r - 1);
    int turn = left / (R - 1);
    int more = left % (R - 1);
    // printf("left: %d turn: %d more: %d\n", left, turn , more);
    if(more == 0) {
        if(turn % 2 == 0) {
            nr = R - 1;
        }
        else {
            nr = 0;
            d = 0;
        }
    }
    else {
        if(turn % 2 == 0) {
            nr = R - 1 - more;
            d = 0;
        }
        else {
            nr = more;
        }
    }
}
// 오른쪽
else if(d == 2) {
    int left = s - (C - c - 1);
    int turn = left / (C - 1);
    int more = left % (C - 1);
    if(more == 0) {
        if(turn % 2 == 0) {
            nc = C - 1;
        }
        else {
            nc = 0;
            d = 3;
        }
    }
    else {
        if(turn % 2 == 0) {
            nc = C - 1 - more;
            d = 3;
        }
        else {
            nc = more;
        }
    }
}
// 왼쪽
else if(d == 3) {
    int left = s - c;
    int turn = left / (C - 1);
    int more = left % (C - 1);
    if(more == 0) {
        if(turn % 2 == 0) {
            nc = 0;
        }
        else {
            nc = C - 1;
            d = 2;
        }
    }
    else {
        if(turn % 2 == 0) {
            nc = more;
            d = 2;
        }
        else {
            nc = C - 1 - more;
        }
    }
}

 

근데 너무 길고 실수하기가 쉽다.

그래서 다른 방법을 찾았는데 초간단한 방법을 찾았다.

여기서는 위치마다, 방향마다 따로 패턴을 구했는데, 위치와 방향을 조합하여 패턴을 파악하는 방법을 찾았다.

만약 좌우로 이동한다 치면, 해당 위치에 돌아오는 데까지 R - 1이 소요된다. 그런데 방향까지 일치하기 위해선 2(R - 1)이 소요된다.

따라서 2(R - 1)의 mod처리를 하면 탐색횟수는 줄어드나 결과는 동일해진다!!! (넘 중요한 꿀팁!)

if (d == 0 || d == 1) {
    s = s % ((R - 1) * 2);
}
else {
    s = s % ((C - 1) * 2);
}

물론 앞선 1번 방식이 시간상 더욱 효율적이긴 하다. while문 자체를 안 쓰고 조건문만으로 결과를 파악할 수 있기 때문이다.그러나 삼성전자 시험에서는 어느 정도 시간 효율성을 얻었으면 최대한 실수할 요소를 줄여서 코드를 적어내는 게 좋기 때문에 2번이 더욱 좋은 방식이라고 생각한다.

 

그리고 또다시 freopen코드를 제거하지 않고 제출해버렸다...;;;

실전에서는 그런 일이 없기를,,,🙏🙏