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

www.acmicpc.net/problem/1783

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

출력

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

---------------------------------------------------------------------------------------------------------

풀이

<C++>

#include <iostream>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N, M; // N : 세로길이, M : 가로길이
	cin >> N >> M;
	
	if (N == 1) {
		cout << 1 << '\n';;
	}
	else if (N == 2) {
		cout << min(4, (M +1) / 2) << '\n';;
	}
	else if (M < 7) {
		cout << min(4, M) << '\n';
	}
	else {
		cout << M - 2 << '\n';
	}

	return 0;
}

기존 체스의 나이트가 왼쪽으로 갈 수 없는 상태라고 생각하면 된다. 맨 왼쪽 아래에 나이트가 있으므로, 무조건 오른쪽으로 1칸 혹은 2칸을 이동해야 하며, 결국 최댓값을 구하기 위해서는 오른쪽으로 1칸 움직이는 두가지의 연산을 반복하게 된다. 케이스를 나눠 생각하면 쉽게 풀리는 문제이다.

 

1. N과 M을 입력받는다

2. N이 1인경우 1을 출력한다.

3. N이 2인경우 4와 (M+1) / 2 중 최솟값을 출력한다.

4. M이 7보다 작은경우 4와 M중 최솟값을 출력한다.

5. 나머지의 경우 (M + 5) - 7 즉, M-2 의 값을 출력한다.