문제는 다음과 같습니다.
일단 문제를 요약하면 다음과 같습니다.
소트한 결과가 사전수능로 가장 뒷서야 하므로
제한된 횟수 S번 내에 첫번째 자리부터 ~ (이후 자리까지) 가장 뒷 번째 수를 가져와야합니다.
⭐️(제한된 횟수 내에서 가져올 수 있는 가장 큰 수 찾기)⭐️
제 전체 코드는 다음과 같습니다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
using namespace std;
typedef long long ll;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
vector<int> v;
int N, S, tmp; cin >> N;
for(int i=0; i<N; i++){
cin >> tmp;
v.push_back(tmp);
}
cin >> S;
vector<int> vv = v;
sort(vv.begin(), vv.end());
for(int i=0; i<v.size() && S>0; i++){
if(v[i] == vv[vv.size()-i]) continue; // 내림차순 정렬이 된 것
int j, cnt=S, max_el = v[i], max_idx = i;
for(j=i+1; j<v.size() && cnt>0; j++, cnt--){ // 대체 원소 찾는 과정
if(max_el < v[j]){
max_el = v[j];
max_idx = j;
}
}
S -= (max_idx - i);
for(; max_idx>=i+1; max_idx--) swap(v[max_idx], v[max_idx-1]); // swap
if(S==0) break;
}
for(int i=0; i<v.size(); i++) cout << v[i] << " ";
return 0;
}
문제 원리는 쉽지만,
특정 알고리즘 유형이 아닌, 시뮬레이션이나 구현, 그리디와 같은 문제가 좀 까다로운 것 같습니다..