99클럽 코테 스터디 10일차 TIL - 병든 나이트 (그리디)

문제: https://www.acmicpc.net/problem/1783
알고리즘 분류: 많은 조건 분기, 그리디 알고리즘, 구현

문제 파악

병든 나이트🐴가 체스판에서 최대한 많은 칸을 방문하는 문제

주요 조건:
1. N × M 크기의 체스판에서 가장 왼쪽 아래 칸에서 시작
2. 병든 나이트는 4가지 이동 방법만 가능

• 2칸 위로, 1칸 오른쪽
• 1칸 위로, 2칸 오른쪽
• 1칸 아래로, 2칸 오른쪽
• 2칸 아래로, 1칸 오른쪽

3. 이동 횟수가 4번 이상이면 모든 이동 방법을 한 번씩 사용해야 함
4. 이동 횟수가 4번 미만이면 제약 없음

접근 방법: 그리디(Greedy) 알고리즘

1. 체스판 크기에 따라 가능한 이동 횟수가 제한 됨
2. 최대 방문 칸 수는, 처음 위치 포함하여 이동 횟수 + 1
3. 이동 방향:

• 모든 이동은 오른쪽으로 이동
• 위/아래 이동은 체스판 경계에 영향을 받는다

4. 4번 이상 이동할 때는 최소 한번씩 모든 방향으로 이동해야 한다

단계별 접근

1. 체스판의 크기에 따라 가능한 최대 이동 횟수를 계산
2. 이동 횟수가 4번 미만인 경우와 4번 이상인 경우를 나누어 처리
3. 4번 이상일 때는 모든 방향을 한 번씩 써야 하므로, 체스판을 벗어나지 않게 이동 방법을 결정해야 함

특수 케이스 처리

N = 1 또는 M = 1인 경우:

체스판이 한 줄짜리면 시작 위치 외에 더 이동할 수 없으므로 1을 반환

N = 2인 경우:

세로가 2칸인 경우 1칸 위로, 2칸 오른쪽과 1칸 아래로, 2칸 오른쪽 두 가지 방법만 사용 가능
➡️ 이 경우 가로로 최대 (M+1)/2 칸까지 이동 가능하지만, 4번까지만 허용 됨

N ≥ 3, M < 7인 경우:

가로 길이가 충분하지 않아 제약 조건을 만족하기 어려운 경우
최대 M개 칸까지 방문 가능하지만, 4칸으로 제한 됨

N ≥ 3, M ≥ 7인 경우:

충분히 큰 체스판에서는 모든 이동 방법을 한 번씩 사용하고 나서도 최적의 방법으로 이동 가능
모든 이동 방법을 한 번씩 사용하면 오른쪽으로 총 6칸 이동하게 됨
그 후로는 1칸 위, 2칸 오른쪽과 1칸 아래, 2칸 오른쪽을 번갈아 사용하여 오른쪽으로 이동
➡️ 결과적으로 M-2개의 칸을 방문할 수 있음

내 코드

const fs = require('fs');
const [N, M] = fs.readFileSync('/dev/stdin').toString().trim().split(' ').map(Number);

function solution(N, M) {
    // 시작 위치 포함하여 최소 1개의 칸은 방문
    if (N === 1 || M === 1) {
        return 1;
    }
    
    // 세로 길이가 1 초과, 가로 길이가 1일 때는 방문할 수 없음
    if (N > 1 && M === 1) {
        return 1;
    }
    
    // 세로 길이가 2일 때는 특별한 경우
    if (N === 2) {
        // 가로로 움직일 수 있는 최대 횟수 (1칸 위로, 2칸 오른쪽 / 1칸 아래로, 2칸 오른쪽만 사용 가능)
        // 이동 횟수는 (M-1)/2 이하이고 최대 4회까지 가능
        return Math.min(4, Math.floor((M + 1) / 2));
    }
    
    // N >= 3, M < 7인 경우 최대 4칸까지만 이동 가능
    if (M < 7) {
        return Math.min(4, M);
    }
    
    // 일반적인 경우, N >= 3, M >= 7
    // 4번 이상 이동할 때 모든 이동 방법을 한 번씩 사용해야 함
    // 모든 이동 방법을 한 번씩 사용하면 오른쪽으로 총 6칸 이동
    // 그 후로는 1칸 위, 2칸 오른쪽 + 1칸 아래, 2칸 오른쪽 조합으로 반복
    return M - 2;
}

console.log(solution(N, M));

참고
https://bedecked-operation-4d1.notion.site/99-10-TIL-1783-1d2eb405261e803fb153f95bec2f86a1