백준 1783번 병든 나이트(자바) - 그리디

병든 나이트 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

8875

3826

3257

42.997%

문제

병든 나이트가 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

예제 입력 2 복사

1 1

예제 출력 2 복사

1

예제 입력 3 복사

17 5

예제 출력 3 복사

4

예제 입력 4 복사

2 4

예제 출력 4 복사

2

예제 입력 5 복사

20 4

예제 출력 5 복사

4

---

풀이 :

1. n == 1일 때 

높이가 1이면 위나 아래로 이동할 수 없기 때문에 무조건 처음에 위치해 있는 그 한 칸만 방문할 수 있다.

if (n == 1)
            result = 1;

2. n == 2 일 때

높이가 2이면 위나 아래로 2칸을 움직일 수는 없고 한 칸 위아래로만 움직일 수 있다.

이때 넓이가 1~2면 이동할 수 없으므로 result = 1이고, 넓이가 3~4면 한 번 이동할 수 있으므로 result = 2이다. 

이처럼 규칙을 찾으면 1 + (m-1)/2가 된다.

* 그런데 이 문제에서 이동 횟수가 4번 이상인 경우는 모든 이동 방법을 다 사용해야 한다고 했는데 이 경우는 2칸 위아래로 이동할 수 없으므로 result가 4를 넘어갈 수 없다.

else if (n == 2) {
            result = 1 + (m-1)/2;
            result = result > 4 ? 4 : result;
}

3. m < 7 일 때

높이가 3 이상인 경우는 2칸 위아래로 자유롭게 이동이 가능하므로 이제 넓이를 고려해줘야 한다. 

가장 많은 칸을 방문하는 경우는 오른쪽으로 한 칸씩 움직이는 경우이다. 따라서 넓이가 4인 경우까지는 오른쪽으로 한 칸씩 움직이면 된다. 하지만 이동 횟수가 4번 이상인 경우는 모든 이동 방법을 다 사용해야하므로 넓이가 5인 경우, 6인 경우 모두 문제의 조건 1번과 4번대로 움직인 후 조건 2번대로 움직일 수 밖에 없으므로 이 경우도 result가 4이다.

else if (m < 7) {
            result = m;
            result = result > 4 ? 4 : result;
        }

 

4. 이 밖의 경우

위의 3번에서 넓이가 7이면 조건 1번 이동, 조건 4번 이동, 조건 2번 이동 후 조건 1번대로 움직일 수 있다. 그러므로 result = 5이고, 넓이가 8이상이면 이제 모든 이동 방법을 다 사용했으므로 다시 조건 1번과 4번을 반복하며 오른쪽으로 한 칸씩 이동하면 된다. 

else {
            result = 4 + m - 6;
        }

 

전체 코드

import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int result;
        if (n == 1)
            result = 1;
        else if (n == 2) {
            result = 1 + (m-1)/2;
            result = result > 4 ? 4 : result;
        }
        else if (m < 7) {
            result = m;
            result = result > 4 ? 4 : result;
        }
        else {
            result = 4 + m - 6;
        }

        System.out.println(result);
    }
}