본문 바로가기

알고리즘 (2020 : 08 : 10 ~ )/완전탐색

[백준 / BOJ] 9881 Ski Course Design (Java)

문제

출처 : https://www.acmicpc.net/problem/9881

 

9881번: Ski Course Design

Farmer John has N hills on his farm (1 <= N <= 1,000), each with an integer elevation in the range 0 .. 100. In the winter, since there is abundant snow on these hills, FJ routinely operates a ski training camp. Unfortunately, FJ has just found out about a

www.acmicpc.net

농부 존의 농장에는 N개의 힐이있다. 농부존은 정기적으로 스키캠프를 운영한다.

불행히도, 농부 존은 이번년도에 새로 개정된 세금 법에 대해 알게되었다. 개정된 법안은 농장에있는 가장 작은 언덕과 가장 높은 언덕의 높이 차가 17초과일때, 스키장으로 인식되어 추가 세금을 내야한다는법이다.

 

농부 존은 이를 막기위해, 자신의 언덕들의 높이를 높이거나 줄이기로했다.

높이 x를 변경하는데, x^2의 비용이 들때, 농부 존이 세금을 안낼수있는 최소비용을 구하는 문제다.


풀이

생각보다 어려웠던 문제다. 처음에는 그리디(매 탐색마다 정렬해가며 가장 작은 언덕과 가장 큰 언덕의 높이를 줄여갔다. 이때, 높이가 동일한 언덕이 나온다면, 지금까지 변경량이 적은 언덕의 높이를 변경시켰다.) 하게 접근했는데, 계속 틀리길래 반례를 생각해보니 다음과 같은 상황에서 최적해를 구하지못했다.

5

1

1

20

21

24

답 : 24

 

가장 작은 언덕에서 늘리는 양과 가장 큰 언덕에서 줄이는 양을 알수없기때문에, 모든 경우를 다 봐줬다.

로직은 다음과 같다.

 

"농부 존의 모든 언덕에대해, 가장 작은 언덕의 높이를 min, 가장 큰 언덕의 높이를 max로 바꿨을때의 최솟값은 얼마인가"

 

max는 자연스럽게 min + 17이 될것이고, 위 물음에 답하는 코드를 만들면된다.

 

    private int calc(int min, int max){
        int ret = 0;
        for(int i = 0; i < N; i++){
            hill.get(i).mass = 0; // 초기화
            if(hill.get(i).height < min) hill.get(i).mass = min - hill.get(i).height;
            if(hill.get(i).height > max) hill.get(i).mass = hill.get(i).height - max;
            ret += Math.pow(hill.get(i).mass,2);
        }
        return ret;
    }

calc함수가 여러번 호출되어서 이전 연산의 값이 지금까지 영향을 미칠수있으므로, 호출시마다 mass를 0으로 초기화 해줬다.


소스코드

https://github.com/devxb/JJUNalgo/blob/master/9881%20Ski%20Course%20Design/Main.java

 

devxb/JJUNalgo

백준 알고리즘 소스코드🙃. Contribute to devxb/JJUNalgo development by creating an account on GitHub.

github.com