[SWEA][C++] 1208. [S/W 문제해결 기본] 1일차 - Flatten

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV139KOaABgCFAYh

SW Expert Academy

 

풀이

주어진 횟수만큼 최고점과 최저점의 차이를 줄여나간다. 정렬을 통해 문제를 해결할 수 있다.

1. 상자의 높이를 오름차순으로 정렬
2. 평탄화 반복
    (1) 상자의 첫 번째 원소(최저점) +1, 마지막 원소(최고점) -1
    (2) 상자를 재정렬
    (3) 주어진 횟수를 모두 사용했거나, 최고점과 최저점의 차이가 1 이하가 되면 반복 종료
3. 최고점과 최저점의 높이 차 반환

코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
    int test_case;
    int T = 10;
    for (test_case = 1; test_case <= T; ++test_case) {
        int cnt;
        vector<int> v(100, 0);

        // 입력
        cin >> cnt;
        for (int &i: v) {
            cin >> i;
        }

        // 연산
        sort(v.begin(), v.end());

        while (cnt--) {
            v.front()++;
            v.back()--;

            sort(v.begin(), v.end());

            if (v.back() - v.front() <= 1) {
                break;
            }
        }

        // 출력
        cout << '#' << test_case << ' ' << v[v.size() - 1] - v[0] << '\n';
    }
    return 0;
}