[백준, JAVA]9881번, Ski Course Design

문제 링크

9881번: Ski Course Design

---

주의사항

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

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

---

문제 설명

---

접근 방법

주관적인 문제 해석!

 

농부 존은 0~100 높이의 N개의 언덕을 농장에 가지고 있습니다.  겨울에 눈이 많이 오면 정기적으로 스키 훈련 캠프를 운영합니다.

 

불행하게도 농부 존은 내년부터 적용될 새로운 세금에 대해 알게 되었습니다. 그러나 공식적으로 가장 높은 언덕과 낮은 언덕의 차이가 17이 초과해야 된다는 것을 발견하였습니다. 그러므로 언덕의 높이를 조절하면 높이의 차 17를 벗어나게 해서 해당 세금을 피할 수 있습니다.

 

높이를 변경할 때에는 (옮긴 높이)²의 비용을 지불합니다. 농부 존이 언덕의 높이를 변경하여 세금에 대하여 회피할 때 가장 적게 지불하는 금액을 결과로 출력합니다.

BFS

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처: https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심

1. 언덕의 높이가 주어집니다.

2. 최대 높이 언덕, 최소 높이 언덕의 높이 차가 17이 미만이 되도록 하는 최소 지불 금액을 결과로 출력합니다.

3. 지불 금액은 (옮긴 높이)²입니다.

 

 

 

알고리즘 진행 순서.

 

1. 입력되는 언덕들의 높이를 받아서 높이의 최대값과 최소값을 구합니다.

 

2. 최대값과 최소값을 기준으로 나올 수 있는 언덕의 차를 모두 구해서 최소 지불 금액을 구합니다.

 

 

 

예제입력 1

 

1. 입력되는 언덕들의 높이를 받아서 높이의 최대값과 최소값을 구합니다.

 

언덕 1 : 20

언덕 2 : 4

언덕 3 : 1

언덕 4 : 24

언덕 5 : 21

 

가장 높은 언덕 : 24

가장 낮은 언덕 : 1

 

2. 최대값과 최소값을 기준으로 나올 수 있는 언덕의 차를 모두 구해서 최소 지불 금액을 구합니다.

 

나올 수 있는 언덕 : 1 - 18, 2 - 19, 3 - 20, 4 - 21, 5 - 22, 6 - 23, 7 - 24

 

1 - 18

언덕 1 : 20 = 20 - 2 = 18(옮긴 높이 : 2)

언덕 2 : 4

언덕 3 : 1

언덕 4 : 24 = 24 - 6 = 18(옮긴 높이 : 6)

언덕 5 : 21 = 21 - 3 = 18(옮긴 높이 : 3)

 

지불 금액 : 4 + 36 + 9 = 49

 

2 - 19

언덕 1 : 20 = 20 - 1 = 19(옮긴 높이 : 1)

언덕 2 : 4

언덕 3 : 1 = 1 + 1 = 2(옮긴 높이 : 1)

언덕 4 : 24 = 24 - 5 = 19(옮긴 높이 : 5)

언덕 5 : 21 = 21 - 2 = 19(옮긴 높이 : 2)

 

지불 금액 : 1 + 1 + 25 + 4 = 31

 

3 - 20

언덕 1 : 20

언덕 2 : 4

언덕 3 : 1 = 1 + 2 = 3(옮긴 높이 : 2)

언덕 4 : 24 = 24 - 4 = 20(옮긴 높이 : 4)

언덕 5 : 21 = 21 - 1 = 20(옮긴 높이 : 1)

 

지불 금액 : 4 + 16 + 1 = 21

 

4 - 21

언덕 1 : 20

언덕 2 : 4

언덕 3 : 1 = 1 + 3 = 4(옮긴 높이 : 3)

언덕 4 : 24 = 24 - 3 = 21(옮긴 높이 : 3)

언덕 5 : 21

 

지불 금액 : 9 + 9 = 18

 

5 - 22

언덕 1 : 20

언덕 2 : 4 = 4 + 1 = 5(옮긴 높이 : 1)

언덕 3 : 1 = 1 + 4 = 5(옮긴 높이 : 4)

언덕 4 : 24 = 24 - 2 = 22(옮긴 높이 : 3)

언덕 5 : 21

 

지불 금액 : 1 + 16 + 9 = 26

 

6 - 23

언덕 1 : 20

언덕 2 : 4 = 4 + 2 = 6(옮긴 높이 : 2)

언덕 3 : 1 = 1 + 5 = 6(옮긴 높이 : 5)

언덕 4 : 24 = 24 - 1 = 23(옮긴 높이 : 1)

언덕 5 : 21

 

지불 금액 : 4 + 25 + 1 = 30

 

7 - 24

언덕 1 : 20

언덕 2 : 4 = 4 + 3 = 7(옮긴 높이 : 3)

언덕 3 : 1 = 1 + 6 = 7(옮긴 높이 : 6)

언덕 4 : 24

언덕 5 : 21

 

지불 금액 : 9 + 36 = 45

 

최소 지불 금액 18을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• 입력값을 저장할 때 Math.max, Math.min을 이용하여 최대 높이와 최소 높이를 구합니다.
• cal함수를 실행하여 모든 언덕의 경우에서 지불하는 금액을 구하였습니다.
• 최소 지불 금액을 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal는 최대 언덕과 최소 언덕에 대하여 만드는 지불 금액을 구하는 함수

 

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

public class Main {
    static int N, max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
    static ArrayList<Integer> elevation = new ArrayList<>();	//언덕 높이 저장 리스트
    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));
        N = Integer.parseInt(br.readLine());
        //1. 입력되는 언덕들의 높이를 받아서 높이의 최대값과 최소값을 구합니다.
        for(int i=0;i<N;i++){
            int temp = Integer.parseInt(br.readLine());
            max = Math.max(max, temp);
            min = Math.min(min, temp);
            elevation.add(temp);
        }
        int answer = Integer.MAX_VALUE;
        //2. 최대값과 최소값을 기준으로 나올 수 있는 언덕의 차를 모두 구해서 최소 지불 금액을 구합니다.
        for(int i=min;i<max-17;i++)
            answer = Math.min(answer, cal(i, i+17));
        if(answer == Integer.MAX_VALUE)	//입력된 언덕으로도 세금을 피할 수 있을 때
            bw.write("0");
        else		//세금 피하지 못할 때 지불 최소 비용 BufferedWriter 저장
            bw.write(answer + "");
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //해당 최대, 최소로 언덕을 바꿀 때 지불 비용 구하는 함수
    static int cal(int min, int max){
        int result = 0;
        for(int i=0;i<N;i++){
            int temp = 0;
            if(elevation.get(i) > max)
                temp = (int) Math.pow(elevation.get(i) - max ,2);
            else if(elevation.get(i) < min)
                temp = (int) Math.pow(min - elevation.get(i), 2);
            result += temp;
        }
        return result;
    }
}