백준 1783

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

---

🧠 문제 핵심 재정리

• 병든 나이트는 총 4가지 이동 방법이 있다:
• 단, 이동 횟수가 4회 이상이면, 4가지 이동방법을 적어도 한 번씩 써야 한다!
• 이 제약은 이동 횟수가 4회 미만일 경우엔 적용되지 않는다!
• 목표는 방문할 수 있는 칸 수의 최대값.

---

✅ 정답 풀이 전략 (정확한 조건 반영)

이동 방법을 보면 공통적으로 오른쪽으로만 이동한다는 점에서 아래처럼 경우를 나눌 수 있어:

1. N == 1

• 위/아래로 2칸 이동 불가능 → 이동 불가
• 방문 칸 수: 1

2. N == 2

• 이동 방법 2, 3번만 가능 (한 칸 위/아래 + 오른쪽 2칸)
• 오른쪽으로 두 칸씩 전진 가능 횟수: (M - 1) / 2 (이동 횟수)
• 방문 칸 수: min(4, (M + 1) / 2)

3. N >= 3

• 모든 이동 가능

➤ M < 7

• 4가지 이동법을 전부 사용 불가능 → 최대 이동 4회 미만 → 제약 없음
  → 방문 칸 수: min(4, M)

➤ M >= 7

• 4가지 이동법 다 쓸 수 있고, 그 이후엔 가장 효율적인 방법만 반복 가능
  → 방문 칸 수: M - 2

---

 

📌 예제 검증

입력 출력 설명

100 50	48	M >= 7, N >= 3 → M - 2
1 1	1	이동 불가
2 4	2	2번, 3번만 가능, 최대 2칸 이동

---

💬 정리 요약

• 핵심은 "이동횟수가 4회 이상이면 4가지 방법 모두 한 번 이상 써야 한다"
• 그래서 M이 7 이상일 때만 4가지 방법 모두 가능하므로 M - 2개 칸 방문 가능!

 

#include <iostream>
using namespace std;

int main()
{
    int N, M;
    cin >> N >> M;

    int result = 0;

    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;
        }
    }

    cout << result << endl;
}