[백준_1783] 병든나이트 (구현, 그리디)

문제

접근법

[1] 5번보다 적은 이동을 하는 경우

 

1-1) 높이 == 1

이동이 불가능 => return 1;

 

1-2) 높이 == 2

높이가 2인 경우는 체스가 위로는 1칸 밖에 이동 할 수가 없다.

 

즉, 모든 경우의 수를 사용할 수 없는 상황이기 때문에 최대 이동 횟수가 4회로 제한이 될 것이다.

 

이동 횟수를 간편하게 찾아내는 방법은 위로 1칸가는 경우 우측으로는 항상 2칸씩 이동해야 하기 때문에 (m+1)/2 를 해주면 나온다!

 

1-3) 높이 3, 넓이 7 이하

 

넓이가 7 이하인 경우에는 오른쪽으로 이동하는 횟수가 제한이 된다.이 때, 위/아래로 2 오른쪽 1 이동하면 4회를 넘길 수는 있겠지만 제한 사항 떄문에 4로 math.min 해주면 된다.

 

[2] 5번보다 많은 이동을 하는 경우

 

이 문제를 풀 때, 알아야 하는 사실은 높이가 3만 되면 그 이후로는 높이에 대한 고려를 하지 않아도 된다는 점이다.

 

우리가 최대로 많이 이동 횟수를 통해 목적지까지 가고싶다면, 어떻게 해야할까? 고민을 해보면 오른쪽으로 적게 이동하면 된다. 

 

즉 가능한 많은 수 만큼 (위/아래2, 오른쪽1) 을 이용하는 것이 정답에 다가가는 방법일 것이다.

하지만, 4회를 초과하는 순간 모든 경우의 수를 사용 해야 하기 때문에, 최초 사용하는 (위/아래1 ,오른쪽2) 의 값을 빼준 "m-2"가 우리의 이동 횟수 일 것이다.

코드

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

public class Main {
    static int n,m;

    public static void main(String[] args) throws Exception {
        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());
        System.out.println(solve(n,m));

    }

    static int solve(int n, int m) {
        if ( n == 1) { // 이동이 불가능 => 1로 리턴한다.
            return 1;
        }
        else if (n == 2) { // 높이가 2일때는, 2칸 위로 작동이 불가능하다.
            // 그리하여 길이가 길어진다고 해도, 4회보다 이동이 적을 때만 규칙과 상관 없는 이동이 가능하기에
            // 4와 이동 가능 횟수를 비교하여 최소 값을 반환해준다.
            return Math.min(4, (m+1)/2);
        }

        else {
            if ( m < 7)  {
                // n ==2 일 떄와 마찬기지로,
                return Math.min(4, m);
            }
            else
                return m-2;
        }

    }
}