[ALGORITHM] 백준 9881 - Ski Course Design

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

9881번: Ski Course Design

대강 해석

존의 농장에는 N(1 <= N <= 1,000)개의 언덕이 있습니다. 각각의 언덕은 0~100의 높이를 가지고 있습니다.

언덕을 깎는대는 x^2 (x는 깎거나 높인 산의 높이) 10 -> 7 (3^2 =9) 10->13 (3^2=9)의 비용이 소모됩니다.

가장 높고 낮은 언덕의 높이 차이가 17이하여야 합니다. 이때 최소비용은 얼마가 드는지 구해주세요.

과정

1. 입력받은 언덕의 높이를 정렬
2. 언덕 높이의 최대값부터 1씩 낮춰가며 어느부분이 최적인지 발견
3. 만약 높이 갱신이 없을 경우 이미 범위 안인 것이므로 0리턴

코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int N;
vector<int> hills;

void Input(){
    cin>>N;
    
    hills.resize(N);
    for(int i=0;i<N;i++)
        cin>>hills[i];
    sort(hills.begin(),hills.end());
}

int calc(){
    int ret=987654321;

    for(int r=hills[N-1], l=hills[N-1]-17;l>=hills[0];r--, l--){
        int sum=0;
        for(int j=0;hills[j]<l;j++){
            sum+=(l-hills[j])*(l-hills[j]);
        }
        for(int j=N-1;hills[j]>r;j--){
            sum+=(hills[j]-r)*(hills[j]-r);
        }
        ret = min(ret, sum);
    }

    if(ret == 987654321)
        return 0;
    return ret;
}

void Solution(){
    cout<<calc()<<'\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    Input();
    Solution();

    return 0;
}