1783 - 병든 나이트

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

처음에는 무슨 탐색문제인가 했다가 N, M 이 2,000,000,000 인거 보고 기겁했다.

차근차근 읽어보니 나이트는 무조건 오른쪽으로밖에 이동할 수 없었다. 그렇다면 말이 방문할 수 있는 최대 칸은 M 일것이다! (1번과 4번을 반복한다면)

근데 N=2 이라면 무조건 오른쪽으로 2칸씩밖에 못 갈것이다. (2번과 3번을 반복) 그럼 최대 칸은 M/2 일 것이다.

N=1 이라면 말은 움직이지 못하고 항상 답은 1칸이다.

하지만 문제의 조건에서 이동 횟수가 4번 이상이면 1~4번을 한번씩은 해봐야 하는 것때문에 상당히 거슬린다.

N=1 은 항상 1이고, N=2 라면 갈 수 있는 최대 칸은 4칸밖에 안된다. (2번과 3번으로는 3회까지밖에 못 움직이기 때문)

위 두가지를 제외하고는 N이 몇이건 상관없다. 4회 이상을 이동할 수 있는 가로의 길이는 최소 7칸이다. 다시말하면, 4회 이상 이동하려면 2칸의 손해를 봐야한다. (1번~4번을 모두 사용하면 2번, 3번 때문에 1칸+1칸을 건너뜀)

정리하면 아래와 같다.

N=1, 답은 1
N=2, 답은 min(4, (m+1)/2)
N>2 이면서 m<7 이면 min(m, 4)
N>2 이면서 그 외의 경우에는 m-2

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    if(n == 1) return puts("1"), 0;
    if(n == 2) return printf("%d", min(4, (m+1)/2)), 0;
    if(m < 7) return printf("%d", min(4, m)), 0;
    printf("%d", m-7+5);
    return 0;
}