[백준] 알고리즘 분류(그리디 알고리즘,JAVA)11497번, 통나무 건너뛰기

문제 링크

11497번: 통나무 건너뛰기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 인접한 통나무로 건너뛰기를 진행합니다.

2. 건너뛰기 난이도는 인접한 통나무 높이의 차의 절대값의 최대값입니다.

3. 통나무를 임의로 배열하였을 때 건너뛰기가 최소값을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 통나무를 높이 기준 오름차순 정렬한 뒤, 난이도가 최소가 되도록 배치를 진행합니다.

 

3. 배치된 통나무의 건너뛰기 난이도를 구해서 결과로 출력합니다.

 

 

통나무 배치하기.

 

건너뛰기 난이도가 최소가 되려면 인접한 통나무의 차이가 최소가 되어야 하기 때문에 아래와 같이 배치되어야 합니다.

 

 

통나무를 위에 같이 배치하기 위해서 높이 기준 오름차순으로 정렬한 뒤

 

배치를 진행하시면 됩니다.

 

예제입력 1.

※1번째 테스트 케이스가 진행되는 과정을 보여드리겠습니다.

 

1. 입력된 정보를 저장합니다.

 

N = 7

높이

 

13

10

12

11

10

11

12

 

2. 통나무를 높이 기준 오름차순 정렬한 뒤, 난이도가 최소가 되도록 배치를 진행합니다.

 

높이 기준 오름차순 정렬

 

10

10

11

11

12

12

13

 

난이도가 최소가 되도록 배치!

 

10

11

12

13

12

11

10

 

3. 배치된 통나무의 건너뛰기 난이도를 구해서 결과로 출력합니다.

 

난이도 구하기!

 

| 10 - 11 | = 1 (height[0] - heigth[1])

 

| 11 - 12 | = 1 (height[1] - heigth[2])

 

| 12 - 13 | = 1 (height[2] - heigth[3])

 

| 13 - 12 | = 1 (height[3] - heigth[4])

 

| 12 - 11 | = 1 (height[4] - heigth[5])

 

| 11 - 10 | = 1 (height[5] - heigth[6])

 

| 10 - 10 | = 0 (height[6] - heigth[1])

 

 

 

1을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 사용하여 통나무 정보를 띄어쓰기 기준 나누었습니다.
• 통나무의 높이 기준 오름차순 정렬한 뒤, 최소 난이도가 되도록 ⌒형태로 통나무를 배치합니다.
• 배치된 통나무의 난이도의 값을 결과로 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

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

public class Main{
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        int[] arr;
        //각 테스트케이스 최소 난이도 탐색!
        for(int i=0;i<T;i++){
            int N = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine()," ");
            arr = new int[N];
            //통나무 정보 저장
            for(int j=0;j<N;j++)
                arr[j] = Integer.parseInt(st.nextToken());
            Arrays.sort(arr);	//높이 기준 오름차순 정렬
            int answer = -1, pre = arr[0];
            //중간 최대값까지 올라가는 중
            for(int j=2;j<N;j+=2){
                answer = Math.max(answer, Math.abs(pre - arr[j]));
                pre = arr[j];
            }
            //N이 짝수일 때
            if(N%2==0)
                N++;
            //중간 최대값에서 내려가는 중
            for(int j=N-2;j>0;j-=2){
                answer = Math.max(answer, Math.abs(pre - arr[j]));
                pre = arr[j];
            }
            //첫 통나무와 마지막 통나무 난이도 구하기
            answer = Math.max(answer, Math.abs(pre - arr[0]));
            bw.write(answer + "\n");	//최소 난이도 BufferedWriter 저장
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();

    }
}