백준 1783번: 병든 나이트

[문제 링크]

1783번: 병든 나이트

---

병든 나이트는 위아래로 이동할 수 있지만 왼쪽으로는 이동할 수 없고 오른쪽으로 밖에 이동하지 못한다.

 

따라서 세로 길이 N의 크기가 얼마인지는 중요하지 않으며, 위아래로 1칸 또는 2칸 이동할 수 있기 때문에 N이 1일 경우 나이트는 어느방향으로든 움직일 수 없고, N이 2일 경우 위아래로 2칸씩 이동할 수 없다. N이 3 이상일 경우 1칸 또는 2칸 자유롭게 이동할 수 있다.

 

또한 오른쪽으로 밖에 이동하지 못하기 때문에 가로 길이 M에 따라 이동할 수 있는 최대 회수가 정해지게 된다.

방문할 수 있는 칸의 최대 개수를 구하기 위해서는 N이 3이상이라는 가정하에 위아래로 2칸, 오른쪽으로 1칸씩 이동하는 방법이 항상 최적해를 보장한다.

 

마지막으로 이동 횟수가 4회 이상일 경우 나이트의 이동 방법을 모두 한번씩 사용해야 한다는 조건을 고려하여 알고리즘을 구현하면 된다.

---

#include <iostream>
using namespace std;

int Greedy(int N, int M)
{
	int cnt = 1;

	if (N == 1)
		return cnt;

	else if (N == 2)
	{
		cnt += (M - 1) / 2;
		return cnt >= 5 ? 4 : cnt;
	}

	else
	{
		if (M >= 7)
			return cnt + 4 + M - 7;
		else
		{
			cnt += M - 1;
			return cnt >= 5 ? 4 : cnt;
		}
	}
}

int main(void)
{
	int N, M;
	cin >> N >> M;

	cout << Greedy(N, M) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 117 day