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

출력

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

---

문제 해결

  병든 나이트의 이동의 경우 일단 3가지로 나눌 수 있다.

 

1. N == 1 인 경우

  1인경우 단 1개의 이동밖에 하지 못하므로 출력은 무조건 1이다.

 

2. N == 2 인 경우

		o				o
o				o

  2번과 3번밖에 사용하지 못한다. 그러므로 3번의 이동을 통해 최대로 방문 할 수 있는 타일은 4개이다. 그 외 경우는 m + 1 / 2로 표를 보면 이해 할 수 있다.

 

3. N == 3 이상인 경우

	o		o		o
o		o		o		o

i) 가로가 6이하인 경우, 1번과 4번 이동을 한 후 2번 또는 3번 이동을 하면 된다. 그전에 탈출하면 그 갯수를 기록하면 된다.

ii) 가로가 7이상인 경우, 2번과 3번을 한번씩하고 나머지는 1번과 4번을 사용하면 된다.

 

  이것을 정리하면 가로가 6이하인 경우에는 1, 2, 3, 4번을 골고루 사용할 수 없으므로 1번과 4번 그리고 2번 or 3번을 사용해서 최대 4개의 타일을 방문 할 수 있다. 그 외 경우는 1번과 4번만을 이용해서 나온 값을 이용하면된다. 바로 m이다. m자체가 1번과 4번만을 이용해서 방문한 타일 갯수이다.

  가로가 7이상이면 2번과 3번을 한 후 1번과 4번을 하면된다. 1번과 4번만 이용하는 경우는 m이므로 m - 2를 하게 해주면 된다. 그 이유는 1번과 4번을 4번을 하는 동안 4개를 방문하는 반면에 2번과 3번은 같은 가로길이에서 2번밖에 방문하지 않는다.

 

#include <iostream>

using namespace std;

int n, m, visitTile;

int main(void) {
	cin >> n >> m;
	
	if(n == 1) {
		cout << 1 << endl;
	}
	else if(n == 2) { // 세로가 두 칸이면 2번과 3번만 가능(최대 3회)
		visitTile = min(4, (m + 1) / 2);
		cout << visitTile << endl;
	}
	else if(n >= 3) {
		if(m <= 6) {
			visitTile = min(4, m);
			cout << visitTile << endl;
		}
		else {
			visitTile = m - 2;
			cout << visitTile << endl;
		}
	}
	return 0;
}