백준 1783번 - 병든 나이트(C++/Greedy/그리디 알고리즘/ 경우의수 분석)

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

1783번: 병든 나이트

문제

병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다. 2칸 위로, 1칸 오른쪽 1칸 위로, 2칸 오른쪽 1칸 아래로, 2칸 오른쪽 2칸 아래로, 1칸 오른쪽 병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다. 체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자. 

접근법

처음에 Pos 구조체 만들어주고 별 헛짓 다하다가, 뭔가 이상해서 다시 생각해본 문제이다.

나이트가 병들어 버려서 오른쪽으로 밖에 이동하지 못하기 때문에, 최적은 위,아래로 오가며 오른쪽으로 한칸씩 이동하는 것이다.

문제가 조건이 다면 그냥  N이 3이상일때 M을 출력해주면 되지만,

조건 ) 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다.

위 조건에 주목해야한다.

 

1. 세로 N 값은 2보다 커야함

1-1 . (1일때는 1출력)

1-2 . 2일때는 M이 7보다 작을땐 판의 (가로크기 + 1/ 2) 만큼만 이동, 그 이후는 4번만 이동가능(조건 충족)

 

2. N이 3보다 크고 && M < 7보다 작을때(4가지 이동 모두 다했을때 가로 이동거리가 +7이다.)

2-1. 위와 비슷하게 반복하며 이동하나 (M) 최대치는 4임 ( 이 이상가면 모든 경우의수가 다 나와야한다)

 

3. M이 7보다 클때

이경우는 시작점을 포함해 4가지 경우의 수를 모두 움직인 5를 더해주고,

7번쨰 칸부터는 위아래로 움직이며 +X쪽으로 1씩 움직일수 있으므로, 시작 좌표값인 7을빼줌 (2번 참조)

즉 M - 7 + 5

 

코드

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int N, M;
	int cntMove;
	cin >> N >> M;
	if (N == 1)
	{
		cntMove =  1;
	}
	else if (N == 2)
	{
		cntMove = std::min(4, (M + 1) / 2);
	}
	else if (M < 7)
	{ // 이동회수가 최대 4번일때 까지, 제한없거나 한번씩 이동할 경우
		cntMove= std::min(4, M);
	}
	else
	{
		cntMove = M - 7 + 5; // 이 이후부턴 위아래로 움직이며 오른쪽으로 한칸씩
	}
	cout << cntMove;
	return 0;
}

 

처음 접근을 너무 어이없게해서 오래걸린 케이스. 오른쪽으로만 간다는것을 핵심으로 두면 사실 경우의수 분리 문제이다.

(사실 출력예시에 너무 큰 힌트가 나와있었다)