[BAEKJOON] 백준 1783: 병든 나이트 (C#)

문제 링크

https://www.acmicpc.net/problem/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보다 작거나 같은 자연수이다.

 

 

출력

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

 

 

 

통과한 답안

namespace _1783
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string[] inputs = Console.ReadLine().Split(' ');
            int N = int.Parse(inputs[0]);  // 세로
            int M = int.Parse(inputs[1]);  // 가로

            int maxMoves = 0;

            if (N == 1)
            {
                maxMoves = 1;
            }
            else if (N == 2)
            {
                maxMoves = Math.Min(4, (M + 1) / 2);
            }
            else
            {
                if (M < 7)
                {
                    maxMoves = Math.Min(4, M);
                }
                else
                {
                    maxMoves = M - 2;
                }
            }

            Console.WriteLine(maxMoves);
        }
    }
}

 

(1, 1)에서 출발하는 나이트가 4가지 방법(↑2→1, ↑1→2, ↓1→2, ↓2→1)으로 이동할 수 있을 때,

N X M 크기의 체스판에서 가장 많이 방문하는 점의 개수를 찾는 문제이다.

단, 이동 횟수가 4회 이상이라면 이동 방법을 모두 1번씩 사용해야 한다는 조건이 있다.

 

이 문제를 해결하기 위해서 모든 경우를 탐색하는 방법이 아닌

크기에 따라서 이동할 수 있는 경우를 나눠서 해결하는 방법을 사용해야 한다.

 

1. 세로의 길이가 1인 경우

세로의 길이가 1이라면 나이트는 이동할 수 없으므로 칸의 수는 1이다.

 

2. 세로의 길이가 2인 경우

세로의 경우가 2라면 나이트는 (2, 1) 혹은 (-2, 1)로만 이동할 수 있으므로

가로의 길이 M에 따라서 최대 이동 칸 수는 달라지는데,

4(이동 횟수가 4회 이상이라면 (1, 2)와 (-1, 2)도 사용해야 하므로)와

M / 2(2칸씩 이동하므로) 중 작은 값이다.

 

3. 가로 길이가 7미만인 경우

가로가 짧아서 모든 이동 방법을 사용할 수 없으므로,

오른쪽으로 이동할 수 있는 칸 수를 계산한다.

따라서 4와 M 중 작은 값이다.

 

4. 그 외의 경우

모든 이동 방법을 사용할 수 있으므로 M에 따라서 칸이 많아지는데,

최소 2번은 오른쪽으로 2칸을 가야하므로, M - 2칸이 최대이다.

 

따라서 위의 경우들을 if문을 이용하여 나눠서 작성하였다.