[백준] 11497 통나무 건너뛰기 - Greedy / Java

• 문제 링크

11497번: 통나무 건너뛰기

 

• 풀이 과정

첫 통나무와 마지막 통나무가 인접해 있다는 조건에 의해, [ 1, 3, 4, 6, 8 ] 의 최소 난이도의 배열을 구하자면

가장 큰 값을 중앙에 기준으로 두고, 양쪽에 점점 작게 배치하여 [ 3, 6, 8, 4, 1 ] 와 같이 구할 수 있다.

 

이는 입력받은 수를 정렬 후, 각 인덱스의 차가 2인 수들을 비교하여 최대값을 갱신해, 해당 값이 최소 난이도가 된다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());

        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());

            int[] arr = new int[n];
            for (int i = 0; i < n; i++)
                arr[i] = Integer.parseInt(st.nextToken());

            Arrays.sort(arr);

            int max = 0;
            for (int i = 0; i < n - 2; i++)
                max = Math.max(max, arr[i + 2] - arr[i]);

            bw.write(max + "\n");
        }

        bw.flush();
    }

}