11497번 : 통나무 건너뛰기

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

11497번: 통나무 건너뛰기

 

 

문제

 

 

코드

import java.io.*;
import java.util.Arrays;

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));
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for(int i=0;i<t;i++) {
            int num = Integer.parseInt(br.readLine());

            String woodStr[] = br.readLine().split(" ");
            Integer woodInt[] = new Integer[num];
            int line[] = new int[num];
            for(int j=0;j<num;j++) {
                woodInt[j] = Integer.parseInt(woodStr[j]);
            }

            Arrays.sort(woodInt);
            int index=0;
            for(int j=0;j<num;j++) {
                if(j%2==0) line[index++] = woodInt[j];
                else line[num - index] = woodInt[j];
            }

            int max = 0;
            for(int j=0;j<num;j++) {
                if(max<Math.abs(line[j]-line[(j+1)%num]))
                    max = Math.abs(line[j]-line[(j+1)%num]);
            }
            sb.append(max+"\n");
        }
        bw.write(sb + ""); bw.flush();
    }
}

 

 

해결방법

처음에 문제 이해가 잘 안 되서 5분동안 문제만 읽었다. 

통나무 건너뛰기의 난이도는 인접한 두 통나무 간의 높이의 차의 최댓값인데 이 최댓값을 최소로 만드는 것이 이 문제의 핵심이다. 

24579 를 25974로 만들었을 때 난이도가 가장 낮아진다. 25974를 계속 보다보니 규칙을 찾았다. 
통나무 높이가 오름차순 정렬되있다고 가정할 때, 가장 작은 통나무부터 시작해 새로운 배열의 맨 왼쪽에다 두고 그 다음 통나무는 맨 오른쪽에다 두는 것을 반복하면 난이도가 가장 낮아지게 통나무를 나열할 수 있다.

 예시)
    2 4 5 7 9        10 13 15 17 19
    2 5 9 7 4        10 15 19 17 13
나열 후에 난이도만 반복문을 통해 찾아주면 문제는 해결된다.

 

슈도코드

1. 테스트 수 입력받기
2. 테스트 수 만큼 반복
     1. 통나무 수 입력받기
     2. 통나무 높이 입력 받아서 오름차순 정렬
     3. line배열에 좌우 번갈아 가면서 정렬된 통나무 놓기
     4. 난이도 구하여 StringBuilder에 붙이기
3. 출력