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

www.acmicpc.net/problem/11497

풀이

가장 높은 통나무를 가운데 세운다! 짝수개면 상위 2개 통나무를 가운데 세운다!

 

그리고 남은 통나무들을 내림차순으로 양 옆으로 배치해나가면 원형을 고려했을 때의 최적해를 구할 수 있다!

 

양 옆에 통나무를 놓을 때 발생하는 높이차가 더 적은 경우로 배치하여 최적 부분 구조가 깨지지 않도록 하자!

구현

통나무를 양 옆에 붙이는 행위를 덱으로 구현하였다.

 

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
 
int t, n;
int res;
 
int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> t;
 
    while (t--)
    {
        res = 0;
        cin >> n;
        vector<int> v(n);
 
        for (int &i: v)
            cin >> i;
        sort(v.begin(), v.end());
 
        deque<int> wood;
 
        if ((int)v.size() & 1)
        {
            wood.push_back(v[n - 1]);
            v.pop_back();
        }
        else
        {
            res = max(res, v[n - 1] - v[n - 2]);
            wood.push_back(v[n - 1]);
            wood.push_back(v[n - 2]);
            v.pop_back();
            v.pop_back();
        }
 
        while (v.size())
        {
            int a = v.back();
            v.pop_back();
            int b = v.back();
            v.pop_back();
 
            int tmp1 = max(wood.front() - a, wood.back() - b);
            int tmp2 = max(wood.front() - b, wood.back() - a);
            if (tmp1 > tmp2)
            {
                res = max(res, tmp2);
                wood.push_front(b);
                wood.push_back(a);
            }
            else
            {
                res = max(res, tmp1);
                wood.push_front(a);
                wood.push_back(b);
            }
        }
        cout << max(res, abs(wood.back() - wood.front())) << '\n';
    }
}