[BOJ] 1783번: 병든 나이트 (c++)

https://www.acmicpc.net/problem/1783

1783번: 병든 나이트

 

그리디

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 입력 : 행 / 열
	int height, width;
	cin >> height >> width;
	
	if (height == 1)
	{
		cout << 1;
	}
	else if (height == 2)
	{
		// 이동 방법 제약 조건 : 방문지점이 5 이상이려면 모든 이동 방법을 사용한 상태여야 함
		cout << min(4, (width + 1) / 2);
	}
	else 
	{
		if (width < 7)
		{
			// 이동 방법 제약 조건 : 방문지점이 5 이상이려면 모든 이동 방법을 사용한 상태여야 함
			cout << min(4, width);
		}
		else 
		{
			// 이동 방법 제약 조건 
			// : 최소 1번씩은 오른쪽으로 2칸 이동하는 방법을 써야함
			cout << width - 2;
		}
	}

	return 0;
}

 

 

병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다.
병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다.

1. 2칸 위로, 1칸 오른쪽
2. 1칸 위로, 2칸 오른쪽
3. 1칸 아래로, 2칸 오른쪽
4. 2칸 아래로, 1칸 오른쪽

병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자.

 

병든 나이트는 체스판의 가장 왼쪽 아래에서 오른쪽(위,아래)으로밖에 이동할 수 없다.

이동방법을 열기준으로 다시 나열하면 다음과 같다.

1. (+2, +1)

2. (-2, +1)

3. (+1, +2)

4. (-1, +2)

 

칸의 최대 개수를 구하려면 오른쪽으로 2칸 이동하는 움직임을 딱 1번씩만 써주면 된다.

그런데...

 

 

 

병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다.
이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다.

 

위 제약조건을 제대로 이해하지 못해서 한참 걸렸다.

그러니까, 방문지점이 5개 미만이면 어떻게 이동하든 상관없고 최대만 되면 되지만

방문지점이 5개 이상이면 이동방법을 모두 한번씩은 사용한 상태여야 한다는 것이다.

음..

 

이걸 그리디적으로 해석하면

방문지점이 4가 되었는데, 위 조건이 가능한 상황이 아니라면 거기서 멈춰야 한다는 것이다. 

이동 방법을 모두 한번씩 사용할 수 있는 상황이란 : 가로길이가 7이상으로 주어졌을 때를 말한다. 

(위 4가지 방법을 모두 사용했을 때 열 좌표값이 7이 되기 때문에. 그리고 세로길이도 충분해야 한다.)

// 위의 긴 문장은 min(4, something)으로 해결된다
...

else if (height == 2)
{
	cout << min(4, (width + 1) / 2);
}
else 
{
	if (width < 7)
	{
		cout << min(4, width);
	}

	...

 

 

 

위에서 가로길이에 대한 분기점을 정했다면, 세로길이에 대한 분기점도 있다.

세로길이가 1일때, 2일때, 3이상일때의 가능한 최대값을 몇번 그려보면 감이 온다.

자세한 사항은 코드를 참고하기..