SW Expert Academy - 1208. Flatten

문제링크

• Flatten

문제설명

• 평탄화는 높은 곳의 상자를 낮은 곳으로 옮기는 방식으로 최고점과 최저점의 간격을 줄이는 작업을 의미한다.
• 가장 높이가 높은 곳의 상자를 가장 높이가 낮은 곳의 상자로 옮기는 작업을 덤프라고 한다.
• 덤프 횟수가 주어질 때 덤프를 모두 수행하고 난 후 최고점과 최저점의 차이를 반환하라
  • 덤프 횟수 이내에 평탄화(최대 높이 차가 0 이나 1인 경우)가 완료되면 그 때의 최고점과 최저점의 높이 차를 반환하라

문제접근

• vector<int> height 에 모든 상자의 높이 정보를 담은 후 오름차순 정렬한다.
• 최고점과 최저점의 높이 차를 구한다.
• 높이 차가 0 또는 1인 경우 평탄화가 완료되었으므로 반복문을 빠져나온다.
• 위 과정을 덤프 횟수만큼 반복한다.

구현

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, char** argv)
{
	int test_case;
	int T = 10;
	freopen("input.txt", "r", stdin);
	for (test_case = 1; test_case <= T; ++test_case)
	{
		vector<int> heightInfo;
		int dumpNum, diff;
		scanf("%d", &dumpNum);
		int height;
		for (int row = 0; row < 100; row++) {
			scanf("%d", &height);
			heightInfo.push_back(height);
		}
		
		for (int cnt = 0; cnt <= dumpNum; cnt++) {
			// 오름차순 정렬
			sort(heightInfo.begin(), heightInfo.end());
			diff = heightInfo[heightInfo.size() - 1] - heightInfo[0];
			if (diff == 0 || diff == 1) break;
			// dump
			heightInfo[0]++;
			heightInfo[heightInfo.size() - 1]--;
			
		}
		printf("#%d %d\n", test_case, diff);
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}