항해99 미들러 알고리즘 10일차

BOJ1783 병든 나이트

 

핵심 조건 

 

• 시작 위치는 왼쪽 아래 모서리입니다. (좌표로 보면 (N, 1) 위치)
• 방문한 칸 수가 5 이상이면, 4가지 이동 방식 모두 한 번 이상 사용해야 함.
• 방문한 칸 수가 4 이하면, 어떤 방법을 쓰든 상관 없음.

결론

1. N == 1 (세로 한 줄)

• 위아래로 움직일 수 없어서 오른쪽으로만 이동 가능함.
• 따라서 제자리만 포함, 최대 1칸 방문.

✅ 정답: 1

---

2. N == 2 (세로 2줄)

• 위로 2칸, 아래로 2칸 이동 못 함. 가능한 이동은 2번, 3번뿐.
• 오른쪽으로 두 칸씩 이동만 가능하므로,
  • (M - 1) // 2 + 1 칸 방문 가능 (처음 위치 포함)

✅ 정답: min(4, (M + 1) // 2)
(4번 이상 이동해도 4가지 방식은 못 쓰니까 제한)

---

3. N >= 3 (세로 3줄 이상)

• 4가지 이동 전부 사용 가능.
• 단, M이 7 이상이어야 모든 이동 방식 다 쓸 수 있음.
• 📌 M < 7: 이동 방식 모두 사용 못 하므로, 최대 4칸까지만 가능
  • ✅ 정답: min(4, M)
• 📌 M >= 7:
  • 정답: M - 2
    • 처음 두 칸은 제약 때문에 못 씀 (다양한 이동 사용 위한 최소 거리 확보)

---

 

---

코드

package hanghee99_Middler;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class hh10_BOJ1783 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int count = 0;
        if(n == 1){
            count = 1;
        } else if(n == 2){
            count = Math.min(4, ((m+1)/2));
        } else if(m<7){
            count = Math.min(4,m);
        } else if(m>=7){
            count = m -2;
        }

        System.out.println(count);
    }

}