코딩테스트/백준

[백준1783] 병든 나이트 - 4가지 이동 조건을 활용한 Java 분기 처리

90만식 2025. 4. 12. 21:10
728x90
사용 언어 : JAVA
문제 : https://www.acmicpc.net/problem/1783
레벨 : 실버3
728x90

✅ 문제 요약

  • dfs 문제라고 생각했으나 입력 값의 범위를 보고 아니라고 판단
  • 패턴을 파악해서 풀이하는 문제
  • 병든 나이트의 패턴(오른쪽으로만 움직일 수 있음)
    • 2칸 위로, 1칸 오른쪽
    • 1칸 위로, 2칸 오른쪽
    • 1칸 아래로, 2칸 오른쪽
    • 2칸 아래로, 1칸 오른쪽
  • 4칸 이상이면 4가지 패턴 모두 사용해야 함.

✅ 문제 설명

 

병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다.

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

병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다.

체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자.

입력

첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다.

출력

병든 나이트가 여행에서 방문할 수 있는 칸의 개수중 최댓값을 출력한다.

 

예제 입력 1

100 50

 

예제 출력 1

48

 

✅ 핵심 아이디어/알고리즘

  • 패턴 정리
    • 패턴 1: (위+2, 오른쪽+1)
    • 패턴 2: (위+1, 오른쪽+2)
    • 패턴 3: (아래+1, 오른쪽2)
    • 패턴 4: (아래+2, 오른쪽1)
  • N==1 일때
    •  사용할 수 있는 패턴이 없음
    • 최초 좌표에 서있으므로 1칸 이동
  • N==2 일때
    • 위,아래 2칸씩 이동할 수 없기 때문에 패턴1, 패턴4 사용 불가
    • 결국 위,아래 1칸씩 이동하고 오른쪽 2칸씩 이동 해야 한다 => (M+1) / 2
    • 이동 횟수가 4번 이상이면 모든방향을 사용해야 하기 때문에 4칸 이상 이동 불가
    • 위 내용을 종합 해보면 아래 수식을 도출할 수 있음.
      • Math.min(4, (M+1)/2)
  • M>=3 && N<7
    • M이 3이상이라 모든 패턴을 다 사용할 수 있다고 생각할 수 있음
    • 하지만 N이 7 이하면 오른쪽 +1,+2,+1,+2 진행 할 수 없어 모든 패턴이 사용 불가
    • Math.min(4,M)
  • M>=3 && N>=7
    • 모든 패턴 다 사용 가능
    • 모든 패턴 사용 후, 더 많은 칸을 사용할 수 있는 패턴1,4 사용
    • M-2

✅ 직접 구현한 코드 (JAVA)

import java.util.*;

public class P1783 {

  public static void main(String[] args) {
      //    2칸 위로, 1칸 오른쪽
      //    1칸 위로, 2칸 오른쪽
      //    1칸 아래로, 2칸 오른쪽
      //    2칸 아래로, 1칸 오른쪽
      // 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다.

    Scanner sc = new Scanner(System.in);

    int N = sc.nextInt();
    int M = sc.nextInt();

    int result = 0;
    if( N == 1){
      result = 1;
    }else if( N == 2){
      result = Math.min(4, (M+1)/2 );
    }else if( N >= 3 && M< 7){
      result = Math.min(4, M);
    }else if( N >=3 && M >= 7 ) {
      result = M-2;
    }

    System.out.println(result);
  }
}

 

✅ 회고 / 배운 점

  • 처음엔 조건이 너무 많고 이동 방식도 헷갈려서 문제 이해 자체가 어려웠음
  • 결국 남들이 정리해놓은 블로그를 보고 파악 하고 모르는 부분을 gpt에 물어보면서 진행
  • 특히 이동 4번 이상일 때, 반드시 4가지 방향을 한 번씩 써야 한다는 조건이 핵심.
  • 이 조건을 기준으로 체스판의 크기에 따라 케이스를 나누는 게 포인트.
  • 문제를 분해해서 이해하고 나니, 간단한 if-else로 해결 가능한 깔끔한 문제
728x90