BOJ 1783번 병든 나이트

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

github : https://github.com/junho0956/Algorithm/blob/master/1783/1783/%EC%86%8C%EC%8A%A4.cpp

 

처음에는 진짜 이걸 어떻게 푸나 싶었다.

범위도 크고 진짜 탐색할수도 없고

그래서 1~4번 규칙을 이용해서 몆가지 예시를 만들어가보니 규칙이 보였다.

 

만약 N 이 1이면 1 2 3 4 조건을 사용할수가 없다. => 1개

만약 N 이 2이면 1 4 조건은 사용못하지만 2 3 은 사용할수있다.  

중요한 것은 만약, 이동 횟수가 4번 이상인 경우에는 위의 이동 방법을 각각 한 번 이상 이용해야 한다. 는 제약이다.

그래서 M 의 길이에 따라 최대 4개가 될 수 있다.

만약 N 이 3이상이라면 1 2 3 4 조건을 모두 사용할 수 있게 된다.

이때는 최대한 많은 방문을 해야한다고 했으니, 규칙상 가로를 2칸이동하는 것 보다는 세로를 2칸씩 이동하는 것이

더 많은 방문을 할 수 있다.

그러므로 2 3 조건을 1번씩만 사용한다면 1 4 조건으로만 계속 1줄씩 채워나갈수 있다

M 의 길이에 주의해서 2 3 조건을 1번씩만 사용하니 방문못하는 경우는 단 2줄밖에 없게 된다.

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    int N, M;
    cin >> N >> M;
    if (N == 1) cout << "1";
    else if (N == 2) cout << min(4, (M - 1) / 2 + 1);
    else {
        if (M <= 6) {
            if (M <= 3) cout << M;
            else cout << "4";
        }
        else cout << M - 2;
    }
 
    return 0;
}