[백준 1783번] 병든 나이트 with Java

guswls·2024년 5월 9일

구현 백준

알고리즘

목록 보기

25/39

문제

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

코드

import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();

		if (N == 1) {
			System.out.println(1);
			return;
		}

		if (N == 2) {
			System.out.println(Math.min(4, (M + 1) / 2));
			return;
		}

		if (N >= 3) {
			if (M < 7) {
				System.out.println(Math.min(4, M));
			} else {
				System.out.println(M - 2);
			}
		}
	}
}

문제 이해

문제에 명시된 4가지 방법으로 밖에 못움직이는 나이트가 체스판 위에 있다.
이때 나이트가 체스판 내에서 도달할 수 있는 영역의 개수를 구해야 한다.
단, 도달할 수 있는 영역의 개수가 4개 이상이 되려면, 4종류의 모든 움직임을 다 사용하여야 한다. 이 조건이 문제를 해결할 수 있는 핵심 조건이다.

풀이 방법

코드를 보면 알겠지만 이번 문제의 경우는 코딩이 별로 필요없는, 규칙찾기 문제이다. 따라서 아래 4장의 사진으로 풀이를 대체한다.

핵심 포인트

N과 M이 각각 20억이하의 정수라는 것을 확인하자.
배열 탐색이 필요한 선형, 혹은 그 이상 차수의 알고리즘으로는 시간내에 해결할 수 없다.

보완할 점 / 느낀 점

사실 딱 문제를 봤을 때 생각할 수 있는 풀이는 아래와 같을 것이다.
- dx, dy로 이동할 수 있는 방향을 정의
- 2차원의 boolean배열을 선언, 이동한 영역을 true로 변경
- 그 개수를 헤아리기
하지만, 입력의 범위를 보고 이러한 풀이가 아니라는 것을 알고 바로 풀이를 찾아봤다.
풀이를 찾아보니 금방 이해할 수 있었지만, 과연 위의 규칙을 실전 코테에서 떠올릴 수 있을 지 모르겠다.
입력 범위를 확인한 후에, 위와 같은 종류의 풀이면 규칙을 찾으려는 시도를 해야될 것이다.