[B0J]병든 나이트(1783번)

티어 : sliver 3
정답여부 : 오답
알고리즘 유형 : 구현, 그리디 알고리즘, 많은 조건 분기
시간 제한 : 2초

💡문제

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

 

💡문제 분석 요약

• 병든 나이트가 4가지 방법으로 움직일수 잇는데 여행하면서 방문의 칸의 수를 최대화하는 수를 출력

 

💡알고리즘 설계

N : 세로

M : 가로

• 세로가 1인 경우 방문할 수 있는 최대의 칸 수는 1이다.
• 만약 세로가 2인 경우는?—> (M+1) / 2칸과 4칸 중 작은 값이 세로 2, M에서 나이트가 최대 방문할 수 있는 칸
• 최대한 방문할 수 있는 방법은 세로가 2인경우 가로 홀수의 칸을 방문한다. 이 방법으로 체스판 가로의 길이가 M인 경우 나이트는 최대 (M + 1) /2칸을 방문할 수 있지만 이동횟수는 4번 미만이여하며 방문 할 수 있는 칸이 최대 4칸이다.
• 그렇다면 가로는 왜 7인건가?—> 그러므로 세로 4이상, 가로가 M일 경우에 방문하는 최대 칸 수는 앞에 모든 이동방법을 사용하는 5칸과 그 이후 방문할 수 있는 M - 7을 더하여 M - 7 + 5가 된다.
• 모든 이동방법을 사용할려면 가로가 최소 7칸이 필요하다 가로가 7칸인 경우 방문하는 최대 칸이 총 5칸이다. 모든 이동방법을 사용해 8칸부터는 제약이 없다. 8칸부터는 최대 가로길이가 M -7 만큼 방문이 가능함

그렇다면 다음 조건식이 만들어진다.

1. 세로가 1인 경우 방문할 수 있는 최대의 칸수는 1
2. 세로가 2인 경우 방문할 수 있는 최대 칸수는 4와(M + 1)/2 중 작은 값
3. 가로가 7미만인 경우 방문할 수 있는 최대 칸수는 4와 M중 작은 값
4. 그외 체스판 경우 방문할수 있는 최대 칸수는 M - 7 + 5

💡시간복잡도

• O(1)

 

💡코드

package algorithms_Java03_07;
import java.util.*;
import java.io.*;

public class baekjoon_1783 {

	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()); // 가로
		if(N == 1) {
			System.out.println(1);
		} else if (N == 2) {
			System.out.println(Math.min(4, (M + 1) / 2));
		} else {
			if(M < 7) {
				System.out.println(Math.min(4, M));
            } else {
            	System.out.println(M - 7 + 5);
			}
		}

	}

}

 

💡 틀린 이유

조건식에서 (M+1)/2 는 생각도 못했던 것 같다.

 

 

💡 느낀점 or 기억할정보

문제의 조건을 만드는게 어려운거 같다.