[그리디 알고리즘] 병든 나이트

예제 입력 1

100 50

예제 출력 1

48

예제 입력 2

1 1

예제 출력 2

1

예제 입력 3

17 5

예제 출력 3

4

예제 입력 4

2 4

예제 출력 4

2

예제 입력 5

20 4

예제 출력 5

4

 

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

1783번: 병든 나이트

- N/M 제한이 2,000,000,000이므로 직접 돌려볼 수는 없다.

- 이동할 수 있는 케이스는 모두 오른쪽으로 이동하는 것 밖에 없으므로 그냥 계산을 통해 구한다.

- Row가 1이면 이동 불가능 == 1 (자기 자신도 세라고 했으므로)

- Row가 2이면, MIN((C+1)/2, 4). (4번 이동하면 모든 방법을 써야하므로, 3번까지만 이동 가능. C+1을 해준 이유는 자기 자신이 포함되어야 하므로.

- Row가 3 이상이고, Column이 7 이상이면, Column 7까지는아래와 같이 문제 조건대로 모든 이동가능한 케이스를 한번씩 다 써준 후, 나머지는 1번 방법+4번 방법을 번갈아 사용해주면 된다. = C-2

- ㄱ

- Row가 3 이상이고, Column이 7 미만이면, 일단 1~4번 이동방법을 모두 사용하는 것이 불가능하므로, 1번 방법+4번 방법을 번갈아가며 사용하되, 3번까지만 이동 가능하다. MIN(C, 4)

 

#include <stdio.h>

inline int MIN(int a, int b)
{
	return a < b ? a : b;
}

int R, C;

int main(void)
{
	scanf("%d %d", &R, &C);

	if (R == 1)
	{
		printf("1\n");
	}
	else if (R == 2)
	{
		printf("%d\n", MIN((C+1)/2, 4));
	}
	else
	{
		if (C >= 7)
		{
			printf("%d\n", C-2);
		}
		else
		{
			printf("%d\n", MIN(C, 4));
		}
	}

	return 0;
}