반응형
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
✅ 문제 풀이
- 상자의 높이를 입력 받은 벡터에서, 가장 큰 값은 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;
}반응형
'CO-TE > 삼성 아카데미' 카테고리의 다른 글
| [DX] 1206번 C++ "view" 풀이/ 구현 (0) | 2023.12.28 |
|---|
