[C++] 백준 온라인 저지 1783번 병든 나이트 풀이

병에 걸린 나이트가 최대 몇 칸 방문할 수 있는지 구하는 문제

 

---

문제의 조건

 

병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다.

 

1. 2칸 위로, 1칸 오른쪽
2. 1칸 위로, 2칸 오른쪽
3. 1칸 아래로, 2칸 오른쪽
4. 2칸 아래로, 1칸 오른쪽

병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다.

체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자.

 

입력

첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다.

 

출력

병든 나이트가 여행에서 방문할 수 있는 칸의 개수중 최댓값을 출력한다.

 

 

풀이

 

 처음엔 체스판에서 움직인다고 해서 BFS 하던 거처럼 바둑판을 탐색해야 하는 줄 알고 DFS로 재귀 탐색하는 코드를 짰는데 예제 1번도 한참을 돌더라고요..ㅋㅋㅋ 무한루프에 빠진 것 마냥...ㅋㅋㅋㅋㅋㅋ 무지했슴다 ㅠ.ㅠ 그래서 이 방향이 아닌거 같아서 질문 게시판을 보니까 저게 아니고 단순 계산 문제였어서 방향을 바꿔서 다시 짜 보았습니다. 

 

 이 문제의 주의사항은 DFS처럼 이동한 모든 칸을 세는 것이 아니고 이동 방법에 따라 도착한 칸 수만 세는 것입니다. 제가 처음에 이게 엄청 헷갈려서 질문 게시판을 찾아 봤었거든요... 문제 설명이 넘 모호함다. 

 

 나이트의 이동 방법을 보면 아래로 움직이던 위로 움직이던 무조건 오른쪽으로 이동을 하게 됩니다. 그런데 아래위로 무조건 한 칸 혹은 두 칸은 이동한 후에 오른쪽으로 이동 하기 때문에 세로의 길이에 따라 나눠서 생각해 볼 수 있습니다.

 

세로 길이가 1인 경우

 만약 세로 길이가 1이라면 이동을 할 수 없습니다. 그렇기 때문에 세로 길이가 1이라면 나이트가 이동할 수 있는 칸의 수는 1칸이 됩니다. 예제 2번을 보면 나이트가 맨 처음에 있는 칸을 방문한 칸 수에 포함한다는 것을 알 수 있습니다. 그렇다면 정답의 최소값은 1이기 때문에 정답을 저장할 변수를 1로 초기화 한 후 세로 길이에 따라 계산을 하면 된다는 것도 알 수 있습니다. 

 

세로 길이가 2인 경우

 세로 길이가 2일 때엔 나이트가 아래위로 한 칸씩은 이동할 수 있습니다. 그렇다는 건 아래위로 한 칸 이동한 후에 오른쪽으로 2칸 이동하는 것이 가능하다는 것을 알 수 있습니다. 그러면 가로 길이가 3보다 크거나 같다면 오른쪽으로 이동할 수 있습니다. 그런데 문제의 조건에서 이동 횟수가 4번 이상일 땐 모든 이동 방법을 한 번씩은 써야 한다고 했기 때문에 만약 가로 길이가 2,000,000,000이어도 최대 3번까지만 이동할 수 있습니다. 이 경우에 방문 가능한 칸은 4칸(처음에 있는 1칸 포함)입니다. 

 그러면 가로 길이가 아주아주 길 때엔 무조건 4칸이 답인 것은 알았는데 가로 길이가 몇 일 때부터 답이 4가 되는지 생각해 볼 필요가 있습니다. 만약 가로 길이가 2라면 아래위로는 이동할 수 있지만 오른쪽으로는 이동할 수 없습니다.

 

 

최소 3칸은 되어야 오른쪽으로 이동할 수 있습니다. 그렇기 때문에 가로 길이가 2 이하일 땐 답이 1이 됩니다. 

 

 

 가로 길이가 3일 때엔 오른쪽으로 한 번만 이동할 수 있기 때문에 답이 2가 됩니다. 

 가로 길이가 4일 때에도 오른쪽으로 한 번만 이동할 수 있기 때문에 답이 2가 됩니다. 

 가로 길이가 5일 때엔 오른쪽으로 두 번 이동할 수 있기 때문에 답이 3이 됩니다. 

 가로 길이가 6일 때에도 오른쪽으로 두 번 이동할 수 있기 때문에 답이 3이 됩니다. 

 가로 길이가 7일 때엔 오른쪽으로 세 번 이동할 수 있기 때문에 답이 4가 됩니다. 드디어 최초로 답이 4가 되는 지점을 찾았습니다. 그러면 가로 길이가 7보다 크거나 같다면 정답으로 4를 출력하고 그렇지 않다면 각 길이에 맞는 답을 계산해서 출력하면 되는데, 3, 4일 때의 답 2에서 맨 처음에 있는 칸 1을 빼면 1칸이 추가된 것임을 알 수 있습니다. 3에서 1을 얻으려면 2로 나눈 몫을 구하면 되고 4에서 1을 얻으려면 2로 나눈 몫에서 1을 빼주면 됩니다. 5와 6의 경우에도 마찬가지입니다. 이 값들에 1을 더해주면 세로 길이가 2일 때의 정답을 구할 수 있습니다. 

 

세로 길이가 3 이상인 경우

 세로 길이가 2인 경우에 답을 구하는 과정에서 나이트가 방문할 수 있는 칸을 결정하는 것은 가로 길이라는 것을 알 수 있었습니다. 그런데 세로 길이가 3 이상일 때엔 아래위로 두 칸 이동하는 것도 가능하기 때문에 가로 길이가 같을 때 세로 길이가 2인 경우에 비해서는 더 많은 칸에 방문할 수 있습니다. 그리고 가로 길이가 충분히 길다면 모든 이동 방법을 사용할 수 있습니다. 세로 길이가 3 이상일 때엔 모든 이동 방법을 한 번씩 사용해야 하는 최소 가로 길이, 즉 언제 이동 횟수가 4 이상이 되는지만 알면 정답을 구할 수 있습니다. 

 

파란색 동그라미는 이동 횟수입니다. 방문 칸수는 이동횟수+1

 

 먼저 이동 횟수가 3일 때엔 위와 같이 이동하면 가장 많은 칸을 방문할 수 있습니다. 가로 길이가 4일 때엔 정답이 4이고 3일 때엔 3, 2일 때엔 2, 1일 때엔 1이라는 것을 알 수 있습니다. 

 그런데 5일 때에도 지금까지 이동했던 것처럼 이동하면 5칸을 방문할 수 있지만 이동 횟수가 4 이상일 때 부터는 모든 이동 방법을 한 번씩은 써야 하기 때문에 지금까지처럼 이동할 수 없습니다. 

 

파란색 동그라미는 이동 횟수입니다. 방문 칸수는 이동횟수+1

 

 최소 이동 횟수가 4 이상이 될 때 부터는 위와 같이 모든 방법을 한 번씩은 써서 이동한 다음에 자유롭게 이동할 수 있습니다. 위 그림을 잘 보시면 가로 길이 7 까지는 모든 이동 방법을 무조건 한 번씩은 써야 하기 때문에 가로 길이가 7일 때엔 최대 5칸에 방문할 수 있습니다. 하지만 가로 길이가 6일 때엔 최대 4칸까지만 방문할 수 있습니다. 아까전에 봤던 그림과 이 그림을 합쳐서 다시 한 번 정리해 본다면 

 가로 길이가 1 = 1칸

 가로 길이가 2 = 2칸

 가로 길이가 3 = 3칸

 가로 길이가 4 = 4칸

 가로 길이가 5 = 4칸

 가로 길이가 6 = 4칸

 가로 길이가 7 = 5칸

 위와 같이 정리할 수 있습니다. 여기서의 공통점들을 모아서 간결하게 코드로 작성하면 가로 길이가 7 이하일 때의 정답을 구할 수 있습니다. 

 

 그런데 입력으로 주어지는 가로 길이의 최대값은 2,000,000,000이니까 7보다 더 길 때에도 정답을 구할 수 있어야 합니다. 

 

 

 두 번째로 봤던 그림을 좀 더 확장시켜 본다면 ④번까지 모든 이동 방법을 한 번씩 써서 이동하고 난 후에는 어떻게 이동하든 상관이 없습니다. 그리고 우리는 방문할 수 있는 최대 칸수를 구해야 하기 때문에 ④번 이후로 ⑤, ⑥ 번째처럼 이동한다면 가장 많은 칸을 방문할 수 있습니다. 그러면 가로 길이 7은 정답 5, 8은 정답 6, 9는 정답 7, 10은 정답 8, ..... 가로 길이 7 이후로는 남은 길이만큼 1씩 늘어납니다. 그리고 가로 길이 7 이후로는 모든 답들이 길이-2 라는 것 또한 알 수 있습니다. 여기까지 코드로 작성하면 모든 입력에 대한 값을 구할 수 있습니다. 

 

 

코드

 

#include <iostream>

using namespace std;

int main()
{
    int height, width;
    cin >> height >> width;
    
    int answer = 1;
    if (1 == height)
        answer = 1; //1칸이면 이동 불가
    else if (2 == height)
    {
        //2칸이면 가로가 3칸 이상일 때 이동 가능
        if (3 > width)
            answer = 1;
        else
        {
            //이동횟수가 4번 이상일 때 부터는 모든 이동방법들을 한 번씩은 써야 하기 때문에 최대 3번까지 이동 가능
            if (7 >= width)
            {
                //가로가 홀수면 2로 나눈 몫만큼 이동 가능
                if (0 != width % 2)
                    answer += width / 2;
                //짝수면 2로 나눈 몫 - 1 만큼 이동 가능
                else
                    answer += width / 2 - 1;
            }
            else
                answer = 4;
        }
    }
    else //3칸 이상일 때
    {
        //가로 길이 3까지는 가로 길이만큼 이동 가능 
        if (3 >= width)
            answer = width;
        //가로 길이 4~6까지는 최대 4칸 방문 가능 
        else if (4 <= width && 6 >= width)
            answer = 4;
        //가로 길이가 7 이상일 땐 가로 길이 - 2
        else
            answer = width - 2;
    }
    
    cout << answer;
    
    return 0;
}