백준 11497번 통나무 건너뛰기

🔒[문제 url]

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

🪄전체 코드

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;

int t,n,l;

void INPUT()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> t;
}


void SOLVE()
{
    while(t--)
    {
        priority_queue<int> q;
        deque<int> wood;

        // INPUT
        cin >> n;
        for(int i = 0; i < n; i++)
        {
            cin >> l;
            q.push(l);
        }

        // Arrange the woods on the easiest level
        // 통나무를 내림차순 정렬한 뒤, 앞뒤로 번갈아가며 삽입한 것이 가장 쉽다.
        for(int i = 0; i < n; i++)
        {
            if(i % 2 == 0) wood.push_front(q.top());
            else wood.push_back(q.top());
            q.pop();
        }

        // 인접한 통나무의 높이를 계산하며 최댓값을 기록한다.
        int ans = 0, front = wood.front();
        for(int i = 0; i < n - 1; i++)
        {
            int first = wood.front();
            wood.pop_front();
            int second = wood.front();

            ans = max(ans, abs(first - second));
        }
        // 가장 첫 통나무와 마지막 통나무 역시 인접해 있다.
        ans = max(ans, abs(front - wood.front()));

        cout << ans << '\n';
    }
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

GOLD5 미만 난이도는 알고리즘 및 풀이 설명을 주석으로 대체합니다.
주석을 참고해주세요.