[백준]Baekjoon1783(Greedy Algorithm)

문제링크 : https://www.acmicpc.net/problem/1783

처리하는 방법이 높이에 따라 3가지로 나뉜다.

1. 높이가 1인경우 -> 제자리 말고 이동할 수 있는 칸이 없으므로 갯수는 1

2. 높이가 2인 경우 -> 2칸씩 위, 아래로가는 1번,4번 방법을 쓸 수 없고

4번이상 이동할 경우 모든 방법을 다 써야하므로 제일 많이 가봐야

제자리 1칸 + 이동 3칸 = 4칸이다, 가로 길이가 충분하지 않은 경우 (M+1)/2 하면

칸의 갯수가 되며 min(4,(M+1)/2)를 통해 구해주면 된다.

(이해가 안될 경우 직접 그리면서 이해해보자.)

3. 높이가 3인 경우

-> 이 때는 너비가 7이상일 떄와 미만일 때로 경우가 나뉘는데 그 이유는

4가지 방법을 모두 쓰면 기본적으로 가로 7의 거리를 가기 때문이다.

고로 7 미만일 때는 min(4, M)을 써주는데

첫 인자가 4인 이유는 4가지 방법을 모두 쓰지 않고 갈 수 있는 최대치가 4이기 때문이고

1번,4번 방법을 썼을 때 오른쪽으로 하나 갈 때마다 하나씩 방문이 가능하므로

두번째 인자가 M이다.

7이상일 때는 4가지 방법을 모두 쓰면 비는 칸이 2,3번 방법을 쓸 때 나오는 2칸 뿐이며

7이후부터는 오른쪽으로 하나 갈때마다 하나씩 방문하면 되므로 M-2의 칸을 방문한다.

아래의 그림과 같은 모양새라고 보면 된다.

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
	int N, M;
	scanf("%d %d", &N, &M);

	int result;
	if (N == 1) result = 1;
	else if (N == 2) result = min(4, (M + 1) / 2);
	else {
		if (M < 7) result = min(4, M);
		else result = M - 2;
	}
	printf("%d\n", result);
}