[Baekjoon/C++] 21557번 - 불꽃놀이

[백준] Baekjoon Online Judge

문제로 이동

 

문제

폴리매스 왕국의 사람들은 불의 돌을 이용해 불꽃놀이를 합니다. 오늘의 불꽃놀이는 $N$개의 폭죽 더미를 이용할 예정입니다.

당신은 아래 작업을 정확히 N-2번 반복해서 폭죽을 터뜨리려고 합니다.

• 양 끝 폭죽 더미를 제외한 폭죽 더미를 하나 고릅니다.
• 해당 폭죽 더미의 폭죽을 모두 터뜨립니다.
• 폭발한 폭죽 더미는 사라지고, 양 옆으로 가장 가까운 폭죽 더미의 높이가 1씩 감소합니다.

불꽃놀이가 끝나고 나면 두 개의 폭죽 더미만이 남습니다. 한 번 불꽃놀이에 사용한 폭죽 더미는 재사용이 불가능하기 때문에, 남은 두 폭죽 더미의 높이 중 더 큰 값을 최소화하려고 합니다. 이 값을 찾는 프로그램을 작성해 봅시다.

 

입력

첫 줄에는 폭죽 더미의 개수 N이 주어집니다. 다음 줄에는 각 폭죽 더미의 높이 A1, A2, ..., AN이 주어어집니다.

 

출력

마지막 두 폭죽 더미 중 더 높은 것의 높이의 최솟값을 출력합니다.

 

---

풀이

#include <iostream>
using namespace std;

int N, arr[200001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    for (int i = 0; i < N; i++) cin >> arr[i];

    for (int i = 0; i < N - 3; i++) {
        if (arr[0] < arr[N - 1]) arr[N - 1]--;
        else arr[0]--;
    }

    cout << max(arr[0], arr[N - 1]) - 1 << '\n';

    return 0;
}

 양 끝의 두 수 중 더 큰 수에 1을 빼는 것을 N - 3번 반복한다. 반복이 끝나면 폭죽 더미가 3개 남고, 이때 폭죽을 터뜨리면 양끝의 폭죽 더미가 모두 1씩 줄어든다. 그러므로 출력할때 1을 빼고 출력해야 한다.