[C++] SWEA 1208 - Flattern

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV139KOaABgCFAYh&categoryId=AV139KOaABgCFAYh&categoryType=CODE

SW Expert Academy

<풀이>

1. 평탄화 작업 횟수와 박스 개수를 입력받는다.

2. 평탄화 작업 수행 후, 최고점과 최저점의 차이를 출력한다.

 

<해법>

1. 평탄화 작업 수행 방법

=> 평탄화 작업에서 중요한 것은 최고점과 최저점 입니다. 평탄화 작업은 결국 최고점에서 최저점에게로 하나 주는 것이기 때문에 중간의 여러 값들은 중요하지 않습니다. 따라서, 정렬을 통해 최고점과 최저점을 구하고 평탄화 작업을 수행합니다.

 

#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 dumpCnt;
        vector<int> box;
 
        //입력
        cin >> dumpCnt;
        for (int i = 0; i < 100; i++) {
            int boxCnt;
            cin >> boxCnt;
            box.push_back(boxCnt);
        }
 
        //박스 개수 순서로 정렬
        sort(box.begin(), box.end());
 
        //평탄화 작업 수행
        for (int i = 0; i < dumpCnt; i++) {
 
            //가장 많은 박스에서 가장 적은 박스로 하나 넘기기
            box.back()--;
            box.front()++;
 
            sort(box.begin(), box.end());
 
            //차이가 1이하인 경우 -> 평탄화 종료
            if (box.back() - box.front() <= 1) {
                break;
            }
        }
 
        //출력
        cout << "#" << test_case << " " << box.back() - box.front() << "\n";
    }
 
    //종료
    return 0;
}

 

구현에 대해 알아볼 수 있는 문제였습니다.