[백준] 1783번 - 병든 나이트 / C++

문제

병든 나이트가 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보다 작거나 같은 자연수이다.

 

출력

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

 

코드

#include <iostream>

using namespace std;

long long N;
long long M;

int main()
{
	long long cnt;

	cin >> N >> M;
	if (N == 1)
		cnt = 1;
	else if (N == 2)
		cnt = min((long long)4, (M + 1) / 2);
	else if (M < 7)
		cnt = min((long long)4, M);	
	else
		cnt = M - 2;
	cout << cnt << endl;
	return 0;
}

 

N과 M의 값에 따라 방문할 수 있는 칸의 최대 개수를 구한다.

N이 1인 경우에는 어디로도 움직일 수 없다. 따라서 방문할 수 있는 칸은 시작 위치 한 칸뿐이다.

N이 2인 경우에는 위/아래로 한 칸, 오른쪽으로 두 칸씩만 움직일 수 있다. 이 경우에는 모든 방향으로 움직일 수가 없으므로 최대 이동 횟수는 3번이고 방문할 수 있는 칸은 최대 4칸이다. 따라서 M의 값에 따라 방문할 수 있는 칸의 수와 4 중에서 작은 값을 선택한다.

N이 2인 경우

N이 3 이상인 경우에는 모든 방향으로 움직일 수 있다. 이동하는 방향은 항상 오른쪽이므로 왼쪽으로 되돌아갈 수 없다. 따라서 오른쪽으로 한 칸씩 이동하는 것이 가장 많은 칸을 방문할 수 있는 방법이다. 이동 횟수가 4번 이상이 되면 모든 방향으로 최소한 한 번씩은 움직여야 한다. 그러기 위해서는 M이 7 이상이어야 한다. 따라서 M이 7 미만인 경우에는 최대 이동 횟수는 3번이고 방문할 수 있는 칸은 최대 4칸이다. M이 7 이상인 경우에는 오른쪽으로 두 칸씩 이동하는 경우 두 가지를 제외하고는 한 칸씩 이동하여 최대 (M-2)개의 칸을 방문할 수 있다.

N이 3 이상이고 M이 7이상인 경우

 

링크

1783번: 병든 나이트

inbdni/Baekjoon