뚝딱뚝딱

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV139KOaABgCFAYh&categoryId=AV139KOaABgCFAYh&categoryType=CODE&problemTitle=&orderBy=INQUERY_COUNT&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1

✅ 문제 풀이

• 상자의 높이를 입력 받은 벡터에서, 가장 큰 값은 1 줄이고, 가장 작은 값은 1 늘리는 식으로 평탄화할 수 있다.
• 한번 덤프를 수행하고 날 때마다, 최소의 상자 높이와 최대의 상자 높이를 갖는 벡터의 위치가 달라진다.
• 이를 쉽게 찾기 위해서 매 덤프마다 벡터를 오름차순 정렬하고 시작하기로 했다.
• 그렇게 하면 벡터의 0번은 항상 가장 작고, 99번은 항상 가장 크기 때문이다.
• 따라서 정렬 후, 벡터의 99번째와 0번째의 차이가 1 또는 0이라면 더이상 상자를 옮기지 않아도 되기 때문에, break문으로 덤프를 멈추도록 한다. 그렇지 않다면, 평탄화가 이루어 져야 하므로 99번째 상자는 하나 줄이고, 0번째 상자는 하나 높여준다.
• 그럼 다음 덤프에서 다시 오름차순 정렬되고, 위의 과정을 반복하면 된다.
• 덤프를 모두 수행하고 나서는, 최종적으로 한번더 오름차순 정렬해준 뒤, 99번째에서 0번째 값을 뺀 값을 출력하도록 하면 된다.

=> 굉장히 naive한 방법이지만, c++ 기준 시간은 10초까지 인정되므로 pass되는 코드이다.

✏ 코드 전문

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

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	for (int i = 1; i <= 10; i++) {
		int n;
		cin >> n;
		vector<int> arr(100);
		for (int j = 0; j < 100; j++) {
			cin >> arr[j];
		}
		
		int answer;
		for (int j = 0; j < n; j++) {
			sort(arr.begin(), arr.end());
			if (((arr[99] - arr[0]) == 1) || ((arr[99] - arr[0]) == 0)) {
				break;
			}
			else {
				arr[99]--;
				arr[0]++;
			}
		}
		sort(arr.begin(), arr.end());
		answer = arr[99] - arr[0];
		cout << "#" << i << " " << answer << "\n";
	}
	return 0;
}