[백준문제풀이] 1783 병든나이트

 

풀이일시 : 2020-09-10

​

 

문제 :

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

ex)

100 50

​

 

출력:

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

ex) 48

​

 

풀이 :

그리디알고리즘

이동횟수가 5 이상이면 네 개의 패턴을 모두 사용해서 이동해야한다. 4 이하이면 뭘 사용해도 상관없다.

​

n=1 이면 시작점에서부터 아무곳도 가지못한다.

​

n=2 이면

​	​	O	​	​	​	O
O	​	​	​	O	​	​

위 표와같이 움직일 수 있을 것이고 4번까지만 사용하고싶은것을 사용할 수 있을 것이다.

m에 따른 result=(m+1)/2 가 될 것이고 만약 result>=4 이면 result=4 (최대) 가 될 것이다.

​

n>=3 이면

​	O	​	​	​	O	​	​
​	​	​	O	​	​	​	​
O	​	​	​	​	​	O	​

계속 나아가도 7 이후에는 result = m-2 가 될 것이고 7 미만이라면 4를 초과해서는 안되는 한에서 어떤 이동이던 가능 할 것이다.

 

#include <iostream>

using namespace std;

int n, m;

int main() {
	cin >> n >> m;
	if (n == 1)
		cout << '1';
	else if (n == 2) {
		if ((m + 1) / 2 > 4) //m이 8이상이게되면 이동횟수가 4번 이상이다.
			cout << 4; //그래서 이동방법에 제약이 생겨 최대 방문갯수는 4로 고정
		else // 그 이하의 크기일때는
			cout << (m + 1) / 2; //높이가 2일때 m을 2로나누면 방문한 갯수가 될 것이다.

	}
	else { //이외에는 제약이 없다.
		if (m >= 7) // m이 7보다 크면 (무조건 한번씩은 써야됨)
			cout << m - 2; //방문한 칸의 갯수는 -2만큼이 될것
		else //m이 그 이하이면
			cout << min(m, 4); //(4와 그 이하의 m 중 하나)
	}
}
​