[C++] 99클럽 코테 스터디 10일차 TIL + 병든 나이트(백준 1783번)

✅ 오늘의 학습 키워드

• 그리디 알고리즘
• 조건문

---

✅ 공부한 내용

✔️  문제 요약

(백준 문제 링크: https://www.acmicpc.net/problem/1783)

 

병든 나이트는 N×M 크기의 체스판에서 왼쪽 아래에서 시작하여 특정 방식으로만 이동할 수 있다:

1. 2칸 위로, 1칸 오른쪽
2. 1칸 위로, 2칸 오른쪽
3. 1칸 아래로, 2칸 오른쪽
4. 2칸 아래로, 1칸 오른쪽

중요한 제약사항은:

• 이동 횟수가 4회 이상이면 네 가지 이동 방식을 모두 한 번씩 사용해야 함
• 이동 횟수가 4회 미만이면 제약 없음

목표는 주어진 체스판 크기에서 방문할 수 있는 최대 칸 수를 찾는 것이다.

✔️  풀이 로직

문제의 핵심은 체스판 크기에 따라 케이스를 나누어 생각하는 것이다:

 

1. N = 1인 경우:

• 세로 길이가 1이므로 위나 아래로 이동 불가능하다.
• 나이트는 모든 이동 방식에서 위나 아래로 먼저 이동해야하기 때문에 N = 1인 경우에는 처음 시작위치를 벗어날 수 없다.
  즉, 현재 방문할 수 있는 칸은 처음 위치인 1개만 가능하다.

 

2. N = 2인 경우:

• 이동 방식 2, 3만 사용 가능 (1칸 위/아래, 2칸 오른쪽)
• 매 이동마다 오른쪽으로 2칸씩 이동 가능
• 최대 방문 칸 수 = min(4, (M-1)/2 + 1)
  • (M-1)/2: 가능한 이동 횟수
  • +1: 처음 위치
  • min(4, ...): 4회 이상 이동 시 모든 이동 방식을 써야 하는데, N=2에서는 불가능하므로 최대 4칸

 

3. N ≥ 3인 경우:

• M ≤ 6일 때:
  • 가로(M)가 6칸 이하인 체스판에서는 1, 4번 이동방식을 이용할 수 있다.
    제약으로 인해 최대 4회 이동 횟수의 방문만이 가능하다.
  • 결과 = min(M, 4)

• M ≥ 7일 때: 그림은 가로(M) 9칸일 때
  • 가로(M)가 7칸 이상인 체스판에서는 1, 2, 3, 4 이동 방식을 모두 이용 가능하다.
  • 결과 = 총 M-2번 여행 가능

 

그러면 의문이 들 수도 있다. 왜 M-2 칸인가???

일단 병든 나이트는 최소 2개의 칸을 낭비한다. 필수적으로 오른쪽으로 2칸을 이동해야 하고
제약 조건에 따라 4회 이상이면 이동 방식 1, 4번도 사용해야 한다.
그렇게 가로칸이 7이상 부터는 직접 체스를 이동을 해보시면 M - 2번이라는 규칙이 나온다. 

 

---

✅ 오늘의 회고

- 😳 어떤 문제가 있었고, 나는 어떤 시도를 했는지

처음에는 동적 계획법(DP)으로 접근하려고 했다. 나이트의 모든 가능한 이동 경로를 탐색하고 최대 방문 칸 수를 계산하려고 했으나, N과 M의 범위가 최대 2,000,000,000으로 너무 커서 완전 탐색이나 DP로는 시간 초과가 발생했다.

- 🤔 어떻게 해결했는지

문제를 더 자세히 분석하며 규칙성을 발견했다. 체스판의 세로 길이(N)와 가로길이(M)에 따라 케이스를 나누어 생각했다.

1. N=1인 경우는 단순히 1칸만 방문 가능
2. N=2인 경우는 특정 이동 방식만 사용 가능하므로 수식으로 표현
3. N≥3인 경우는 M의 크기에 따라 두 가지 케이스로 분류

N≥3, M≥7인 경우가 중요했다. 이때는 4가지 이동 방식을 모두 한 번씩 사용한 후, M-2칸을 방문할 수 있다는 규칙을 발견했다.

- 🤩 무엇을 새롭게 알았는지

• 여전히 문제를 보고 어떤 알고리즘으로 풀어야할지는 어려운 것 같다. 계속 문제를 풀다 보면 유형이 보일 것이라 생각한다. 일단 처음에 생각했던 알고리즘으로 풀어보고 안되면 다른 알고리즘으로 해야지 않을까 싶다. 
• 문제의 특성에 따라 그리디 접근법이 동적 계획법보다 효율적일 수 있다는 점을 배웠다.
• 큰 입력 범위(2,000,000,000)가 주어진 경우, 매우 크기 때문에 O(NxM) 또는 그 이상의 시간 복잡도를 가진 알고리즘은 시간 초과가 발생한다고 한다. 그래서 수학적 규칙성을 찾아 O(1) or O(log N)과 같은 시간 복잡도로 문제를 해결하는 방법을 떠올라야...한다네..? 흠...

---

✅ 전체 코드

#include <iostream>
#include <algorithm>

using namespace std;

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

    int result;
    
    if (N == 1) {
        result = 1;
    }
    
    else if (N == 2) {
        result = min(4, (M - 1)/2 + 1);
    }
    
    else { 
        if (M <= 6) {
            result = min(M, 4);
        }
        else {
            result = M - 2;
        }
    }

    cout << result << '\n';
    
    return 0;
}