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

✅ 문제

https://www.acmicpc.net/problem/1783

✅ 분류

• 그리디 알고리즘

✅ 공부한 내용

- 문제 요약

• 병든 나이트가 N (세로) x M (가로) 크기 체스판의 가장 왼쪽 아래 칸에 위치해있다. 4가지 방법으로만 움직일 수 있다.
• (x, y) 좌표로 생각하고 표현
  (1, 2) : 1칸 오른쪽, 2칸 위로
  (2, 1) : 2칸 오른쪽, 1칸 위로
  (2, -1) : 2칸 오른쪽, 1칸 아래로
  (1, -2) : 1칸 오른쪽, 2칸 아래로
• 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야한다.
• 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 제약이 없다.
• 방문할 수 있는 칸의 최대 갯수를 구하기

- 풀이 로직

• N과 M 크기에 따라 이동 방법이 다르고 횟수도 다르다고 생각해서, 크기에 따른 조건을 생각했다.

• N이 1일 때,오른쪽으로 이동하지 못하기 때문에 최댓값은 1이다.
  
  
• N이 2일 때, 이동가능한 방향은 좌표(x,y)로 표현을 하면 (2, 1) 또는 (2, -1)이다.
  위/아래로 2칸 움직일 수가 없어서 나머지 (1,2)와 (1,-2) 로 이동할 수 없다.
  출발 포함해서 먼저 한 칸 밟고, 오른쪽으로 두 칸씩만 가서 밟는 형식.
  
  이런 식으로 진행하면
  M이 1 혹은 2 -> 1칸 방문
  M이 3 혹은 4 -> 2칸 방문
  M이 5 혹은 6 -> 3칸 방문
  
  (M+1) / 2 칸 방문 가능
  문제 조건 상 최대 4칸 이상 방문하지 못하기 때문에
• min(4, (M + 1) / 2)
  
  
• N이 3이상이고, M이 7미만일 때
  공간이 좁아서 오른쪽 이동 칸 수가 부족해서 4가지 이동 방식을 다 못 쓴다. (그림을 그려서 확인하면 더 쉬움)
  최대 방문 칸 수 = 오른쪽으로 가면서 M칸
• min(4, M) 
  
  
• N이 3이상이고, M이 7이상일 때
  4가지 이동 방향을 모두 한 번씩 써야 한다면 최소 4번의 이동이 필요하다. (문제 조건)
  이 조건이 가능한 최소 M이 7이다.
  충분히 커서 4가지 이동 방식 다 사용 가능
  초기 4번 이동 방식 사용 후, 무조건 오른쪽으로 가는 게 최대 이동
• M - 2 

✅ 회고

그리디 알고리즘에 점점 익숙해져 가고 있는데, 이런 문제는 확실히 직접 그려서 확인해가면 푸는게 확실한 것 같다.

처음엔 헷갈렸지만, 직접 그리니 패턴이 보였다.

✅ 풀이

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

public class Main {
    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()); // N : 세로 길이
        int M = Integer.parseInt(st.nextToken()); // M : 가로 길이

        int answer = 0; // 방문할 수 있는 칸의 최댓값

        if (N == 1) {
            answer = 1;
        } else if (N == 2) {
            answer = Math.min(4, (M + 1) / 2);
        } else {
            if (M < 7) { // M >= 3, M < 7 인 경우
                answer = Math.min(4, M);
            } else { // M >= 3, M >= 7 인 경우
                answer = M - 2;
            }
        }

        System.out.println(answer);
    }
}