BOJ 1783 - 병든 나이트

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

병든 나이트가 존재한다. 체스판에서의 총 4가지의 이동방법이 있을때
최대로 방문할 수 있는 발판은 몇개인가?

※ 방문 발판이 4개이하일때는 이동의 제약이 없으나, 5개이상부터는 모든 방법을 한번씩 사용하여야 한다.

Solution

우선 n과 m을 height, width로 가정하겠다.

나이트의 이동방법을 보면 항상 오른쪽으로 간다는것을 알 수 있다.

그렇다면 height의 값에 따라 방문횟수를 일반화 할 수 있다.

만약 height 가 1이라면

위와 같이 나이트가 이동할 공간이 없다. 이 때 답은 1이 나올것이다.
(처음 시작 발판도 방문점으로 취급함)

다음 height 가 2라면

위로 , 아래로 1칸씩 이동하는 2번방법과 3번방법이 사용 가능하다.
대신 이때는 width의 크기에 무관하게 1번방법과 4번방법을 사용할 수 없다.
그래서 정답으로 나올수 있는 최대값은 4이며 , width의 값에따라 더 작아질 수 있다.

이후 height >= 3 이라면

우선 width가 7이상이라면 4가지의 방법 모두 사용할 수 있다.
이후에는 오른쪽으로 한칸씩만 가는 1번 방법과 4번 방법을 반복하는것이 가장 많은 발판을 방문할 수 있는 루틴일것이다.

만약 4가지의 방법을 다 사용할수 없게 width < 7 이라면, 최대값은 4가 될것이고 그 이하는 width의 크기와 같을것이다. 1번 방법과 4번 방법을 반복적으로 사용하면 되기때문.

Code

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int height, width;

    cin >> height >> width;

    if (height == 1) {
        cout << 1;
        return 0;
    }

    else if (height == 2) {
        cout << min(4,(width+1) / 2 );
        return 0;
    }

    else if (height >= 3) {
        if (width >= 7) {
            int ans = 5;
            width -= 7;
            ans += width;

            cout << ans;
            return 0;
        }

        else {
            cout << min(4,width);
            return 0;
        }
    }
    return 0;
}

참고 : https://code.plus/course/43 , 그리디 알고리즘(연습)