문제 개요

N개의 돌들이 1번부터 N번까지 순서대로 놓여 있으며, 각 돌에는 하나의 숫자가 적혀 있습니다. 1번에서 시작하여 K의 거리로 점프하면서 N번 돌에 도달할 때, 지나온 돌들에 적힌 숫자들의 최댓값 중 최소를 구하는 문제입니다.

접근 방법

코드 A

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
		}

		for (int i = Math.max(arr[0], arr[n - 1]); i <= 100; i++) {
			int lastIdx = 0;
			boolean success = true;
			for (int j = 0; j < n; j++) {
				if (arr[j] > i)
					continue;

				if (j - lastIdx > k) {
					success = false;
					break;
				}
				lastIdx = j;
			}

			if (success) {
				System.out.println(i);
				break;
			}
		}
	}
}

핵심

• 처음과 마지막은 반드시 거쳐가야 한다
• 최소값을 구하는 문제의 정답이 arr[0]이나 arr[n - 1] 보다 작을 수 없다.
• 최소값에 집중하여, 최소값이 나오는 순간 loop를 종료한다.
• 추가적인 메모리 사용 없이 lastIdx를 사용하여 점프 거리를 측정한다.

---

코드 B

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
		}

		int ans = 101;
		for (int i = 100; i >= 1; i--) {
			int cnt = 0;
			int[] tmp = new int[n];
			for (int j = 0; j < n; j++) {
				if (arr[j] > i) continue;
				tmp[cnt++] = j;
			}

			boolean success = tmp[0] == 0;

			for (int j = 1; j < cnt; j++) {
				int diff = Math.abs(tmp[j] - tmp[j - 1]);
				if (diff > k) {
					success = false;
					break;
				}
			}

			if (!success) break;

			ans = Math.min(ans, i);
		}

		System.out.println(ans);
	}
}

핵심

• 최댓값을 i로 가정하고, i 이하의 값만 밟을 수 있는 경로를 구성한다.
• 가능한 인덱스들을 저장한 배열을 활용하여 연속적인 점프가 K 이하인지 확인한다.
• 최댓값을 줄여가며 점프 가능 여부를 검사하고, 가능한 최소 최댓값을 갱신한다.
• 불가능한 경우 루프를 중단하여 불필요한 탐색을 줄인다.