[백준 BOJ] 11497 통나무 건너뛰기

11497_통나무 건너뛰기

링크

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

 

풀이

 

통나무 건너뛰기의 최소 난이도를 구하는 문제입니다.

난이도는 인접한 통나무의 높이차의 최댓값으로 결정됩니다.

 

그렇다면 어떻게 통나무를 배열해야 가장 작은 높이차를 만들 수 있을까요?

 

통나무의 높이를 내림차순으로 정렬한 후, 가장 큰 값을 가운데에 두고 왼쪽 오른쪽 번갈아 가면서 놓으면 됩니다.

 

왼쪽 오른쪽 번갈아 놓기 때문에 중간에서의 높이차는 2칸 떨어진 통나무의 높이차가 될 것이고, 예외로 연결되는 통나무인 첫 번째와 마지막 번째 통나무의 높이차가 1칸 떨어진 통나무의 높이차가 더 추가됩니다.

 

그렇게 해서 max 값을 구해주면 그 통나무 건너뛰기의 난이도가 됩니다.

 

 

코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

//15553_난로 #include <cstdio> #include <algorithm> #include <queue> using namespace std;   priority_queue<int> pq; int n, k; int t1, t2; int startnum, endnum; int ans;   int main() {     scanf("%d %d", &n, &k);     scanf("%d", &t1);     startnum = t1;       for (int i = 2; i <= n; ++i) {         scanf("%d", &t2);         pq.push(t2 - t1 - 1);         t1 = t2;     }       endnum = t1;     ans = endnum - startnum + 1;       while (--k) {         ans -= pq.top(); pq.pop();     }       printf("%d\n", ans);       return 0; }

cs