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

오늘의 학습 키워드

• 구현
• 조건 분기
• 최대값 탐색
• 체스판 이동

---

공부한 내용 정리

병든 나이트는 보통 나이트보다 움직임이 제한된 형태로, 4가지 방향으로만 이동할 수 있다.

목표는 체스판 위에서 가능한 많은 칸을 방문하는 것이고, 이동 횟수가 4번 이상이면 네 가지 이동을 모두 써야 한다는 제약이 추가된다.

따라서, 체스판 크기(N, M)에 따라 조건을 분기해서 접근해야 했고, 각각의 경우를 다음과 같이 나눠서 풀었다.

• N == 1: 위아래 이동 자체가 불가능 → 방문 칸 수는 무조건 1
• N == 2: 2, 3번 움직임만 가능 → (M + 1) / 2 만큼 오른쪽 이동 가능, 최대 4칸
• N >= 3 && M < 7: 네 방향 모두 쓰지 못함 → 최대 4칸까지만 이동 가능
• N >= 3 && M >= 7: 모든 움직임 사용 가능 → M - 2칸까지 이동 가능

---

소스코드

/*
병든 나이트
입력 : N M = 20억 이하 수
      N : 세로 길이 M : 가로길이
로직 : 왼쪽 아래서 출발함 0,0 아니고 N,0
      병든 나이트의 이동 횟수가 4번보다 적지 않다면, 
      이동 방법을 모두 한 번씩 사용해야 한다.
      이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 
      이동 방법에 대한 제약이 없다.
      
      1. 2칸 위, 1칸 오른쪽 (-2, +1)
      2. 1칸 위, 2칸 오른쪽 (-1, +2)
      3. 1칸 아래, 2칸 오른쪽 (+1, +2)
      4. 2칸 아래, 1칸 오른쪽 (+2, +1)
      
      if 
      N = 1 정답 : 1 이동불가
      N = 2 M = 1 > 1번 
      오른쪽으로 갈 수 있는 횟수는 (M-1)/2
      이동횟수가 4번 넘으면 제약이 생김 최대 4칸 까지 가능
      
      N = 3 M = 4 일때
      4가지 다 못감
      이동가능한 만큼만 최대 이동 최대 M만큼 가능
      N = 3 M = 6 일때
      최대 4번 이동 가능
            
      N = 3 M = 7일때
      4가지 방향 다 가능 5번 이동
출력 : 이동거리
*/

import java.util.*;
import java.io.*;

public class Main {
  public static void main(String[] args) throws IOException {
    // ---- 입력
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] input = br.readLine().split(" ");
    
    long N = Long.parseLong(input[0]);
    long M = Long.parseLong(input[1]);
    
    // ---- 로직
    if (N == 1)
      System.out.println("1");
    else if(N == 2)
      System.out.println(Math.min(4, (M + 1) / 2));
    else if (N >= 3 && M < 7)
      System.out.println(Math.min(4, M));
    else
      System.out.println(M - 2);

  }
}

---

오늘의 회고

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

처음엔 단순히 움직일 수 있는 칸 수를 시뮬레이션으로 세보려 했는데,

문제 조건이 명확히 나뉘는 경우가 많아서 조건 분기로 푸는 게 훨씬 깔끔하다고 판단되었다.

 

• 어떻게 해결했는지

체스판 세로 길이 N과 가로 길이 M에 따라 분기하여 각각에 맞는 공식으로 계산했다.

N == 2일 때는 (M + 1) / 2 공식이 포인트였고, M >= 7일 때는 네 가지 움직임을 모두 사용 가능해서 M - 2가 답임을 알았다.

 

• 무엇을 새롭게 알았는지

단순 구현이 아니라 문제 조건을 수학적으로 분석해서 공식화하면 훨씬 효율적으로 문제를 풀 수 있다는 걸 배웠다.

 

• 내일 학습할 것은 무엇인지

내일은 BFS 문제를 집중적으로 풀어보면서, 탐색 로직을 완전히 익혀 보겠다.

---