알고리즘/문제

(22.06.19) (Baekjoon) 1783.병든 나이트

Job_E 2022. 6. 22. 01:37

 

 

1783번: 병든 나이트

첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다.

www.acmicpc.net

시간 제한 : 2초

메모리 제한 : 128 MB

 

 

문제

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

 

최적의 상황을 찾는 그리디 알고리즘을 사용하는 문제다.

이 문제의 해결은 다음과 같은 상황으로 나누어 풀이하면 가능하다..

 

i) N == 1

ii) N == 2

iii) N == 3

iii-1) M < 7

iii-2) else

위 5가지 경우만 제대로 해결할 수 있으면 어렵지 않게 풀 수 있다.

다만, 최대 이동 값이 4를 넘어가는 경우엔 4가지 이동이 모두 한번 이상은 이뤄져야 한다는 걸 알아두고 접근하자.

 

i) N == 1(세로 길이가 1일 경우)

우선 N = 1인 경우, 어떤 이동도 불가능하고, 시작점도 이동값에 포함시키기 때문에  M과 관계없이 최댓값은 1이 나온다

ii) N == 2(세로 길이가 2인 경우)

 N = 2인 경우, 

  1. 1칸 위로, 2칸 오른쪽
  2. 1칸 아래로, 2칸 오른쪽

 

이 두가지 경우밖에 이동할 수 없다.

또한, 4번째 이동시 위치하는 7번째 칸 이후로부턴 칸이 더 이어져 있어도

y값이 2만큼 변하는 나머지 이동을 진행할 수 없기 때문에 N=2인 경우의 이동 최댓값은 4 or M/2를 반올림한 값으로 결정할 수 있다.

 

iii) N == 3(세로가 3인 경우)

세로가 3인 경우, M이 7 이상이 되면 모든 이동을 하고 진행할 수 있다.

위 이미지에서 볼 수 있듯, 모든 이동을 한번씩 진행하고 나면 x값이 7만큼 이동한 걸 확인할 수 있다.

 

그리고 그 이후로부턴 

iii-2) N >=3 && M >= 7

x가 오른쪽으로만 이동할 수 있으므로, 

  1. 2칸 위로, 1칸 오른쪽
  2. 2칸 아래로, 1칸 오른쪽

이 두 이동을 반복함으로써 x값을 1씩 더해가면서 x의 최댓값까지 최댓값으로 이동할 수 있다.

 

즉, 이때 구해지는 최댓값은 M - (처음 이동한 7칸 - 5번의 이동) == M-2가 된다.

 

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

public class Main {
	static int[] dy = {-2,-1,1,2};
	static int[] dx = {1,2,2,1};
	static long N,M;
	static Long ans = Long.MIN_VALUE;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Long.parseLong(st.nextToken());
		M = Long.parseLong(st.nextToken());
		
		/*
		 	2칸 위로, 1칸 오른쪽
			1칸 위로, 2칸 오른쪽
			1칸 아래로, 2칸 오른쪽
			2칸 아래로, 1칸 오른쪽 
		 */
		
		move();
		
		System.out.println(ans);
	}

	
	static void move() {
		if(N == 1) {
			ans = (long) 1;
			return;
		}
		else if(N == 2) {
			if(M < 7) {
				ans = (long) Math.round((M*1.0)/2);
			}
			else {
				ans = (long)4;
				return;
			}
		}
		
		else if(N >= 3) {
			if(M < 7) ans = Math.min(4, M);
			else {
				ans = M-7+5;
			}
		}
		
	}
	
}

 

유연한 생각이 필요한 문제였다.

그리디 관련 문제를 많이 풀어봐야겠다.