[BOJ] 9881 : Ski Course Design

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

---

[ 문제해석 ]

 N개의 언덕을 가지고 있는데 가장 높은 언덕와 가장 낮은 언덕의 차이를 17 이내로 만들어야된다. 언덕을 k 만큼 쌓거나 깎는데 k * k 만큼의 cost가 발생한다. 이때, 필요한 가장 적은 cost는 얼마인가

 

[ 알고리즘풀이 ]

 N 은 최대 1000, 언덕의 높이도 0 ~ 100 으로 범위가 작다. 즉, 모든 경우에 대해서 cost를 구해봐도 시간 초과에 걸리지 않는다.

 --> 0 ~ 17 / 1 ~ 18 / 2 ~ 19 / .... / 83 ~ 100 과 같이 크기가 17인 모든 범위를 나눈 후, 각 범위마다 N개의 언덕을 순회하며 깎거나 쌓아본다.

 

[ 코드 C++ ]

#include<iostream>
#include<algorithm>
using namespace std;
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int N, hills[1000];
 
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> hills[i];
 
    int ans = 99999999;
    for (int i = 0; i <= 100 - 17; i++) {
        // i ~ i + 17 까지가 우리가 잡은 범위!
        int tempAns = 0;
        for (int j = 0; j < N; j++) {
            if (hills[j] < i) tempAns += (i - hills[j]) * (i - hills[j]);
            if (hills[j] > i + 17) tempAns += (hills[j] - i - 17) * (hills[j] - i - 17);
        }
        ans = min(ans, tempAns);
    }
    cout << ans << '\n';
}

[ github ]

github.com/travelbeeee/ProblemSolving/blob/master/BOJ/BOJ9881.cpp

travelbeeee/ProblemSolving

---