[백준] 1738번 병든 나이트

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;

int main () {
    fastio;
    int n, m;
    
    cin >> n >> m;
        
    if (n == 1) cout << 1;
    else if (n == 2) cout << min(4, (m + 1) / 2);
    else if (m < 7) cout << min(4, m);
    else cout << m - 2;
}

[참고]

https://novlog.tistory.com/entry/CC-BOJ%EB%B0%B1%EC%A4%80-1783-%EB%B3%91%EB%93%A0-%EB%82%98%EC%9D%B4%ED%8A%B8-%EB%AC%B8%EC%A0%9C-%ED%92%80%EC%9D%B4-%EC%86%8C%EC%8A%A4-%EC%BD%94%EB%93%9C

 

[설명]

병든 나이트; 

여행하는 칸 수 최소로

이동횟수가 4보다 크면 이동 방법을 모두 한 번씩 사용해야 함

4보다 작거나 같으면 제약이 없다

-> 칸의 방문 개수 중 최댓값 출력

 

[풀이]

4가지 방법을 1번씩 사용하면 오른쪽으로 최대 6칸까지 갈 수 있다.

이동 횟수가 4를 넘으면 1~4번 방법을 모두 1번씩은 사용해야 하므로 m을 7 미만으로 한정해야한다.

[1] (m+1)/2는 왜 나옴?

세로가 2면 (m-1)/2 + 1인데 

이는 세로 개수 m에서 시작점 1개를 빼고  (m-1)

2칸씩 이동하므로 2를 나눠서 갈 수 있는 칸수를 구한다.

이후 시작점 1개도 칸수로 고려해서 1을 더해서 (m+1)/2가 나온 것이다.

[2] m-2는 왜 나옴?

병든 나이트는 처음 시작한 칸도 방문한 칸 1개로 세기 때문에 이동 횟수는 총 m - 1번까지 가능

하지만 문제 조건상 4가지 방법을 다 사용하려면 처음에 2칸은 소모해야 함(위아래 포함해서 방향 전환해야 하니까)

그래서 최대로 갈 수 있는 칸 수는 m - 2칸 정도가 된다.

즉 2칸은 위아래 이동(방향 전환)을 위해 사용되고 나머지 8칸만 실제 오른쪽으로 유의미하게 이동한다.

4가지 다 쓰려면 위 → 아래 → 위 → 아래 식으로 움직여야 하므로 방향 바꾸는 데 최소 2칸 소모됨