간단하다. 뒤에서부터 보면서 앞에게 더 크면
앞에것(v[i]) 를 v[i], v[i+1]-1 중 더 작은 것으로 만들어주면 오름차순이 된다.
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,a,cnt;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
vector<int> v;
for (int i = 0; i < n; i++) { cin >> a; v.push_back(a); }
for (int i = n - 2; i >= 0; i--) {
if (v[i] < v[i + 1]) {
// 아무것도 안해도 ㅇㅋ
}
else {
// v[i]를 min(v[i], v[i+1]-1)로 만든다
if (v[i] <= v[i + 1] - 1) {
// ㅇㅋㄷㅋ
}
else {
// 예를 들어 7 5 이렇게 있으면
// 7을 4로 만들어줘야함. 차이는 3이다.
int diff = v[i] - v[i + 1] + 1;
v[i] = v[i + 1] - 1;
cnt += diff;
}
}
}
cout << cnt;
return 0;
}
처음에 작성한 코드는 알아보기 쉽게 이렇게 썼는데
맞았습니다!! 를 확인하고 일케 보기 편하게(ㅋㅋ) 바꿨다
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,a,cnt;
int main() {
cin >> n; vector<int> v;
for (int i = 0; i < n; i++) { cin >> a; v.push_back(a); }
for (int i = n - 2; i >= 0; i--) {
if(v[i] > v[i+1] -1) {
int diff = v[i] - v[i + 1] + 1;
v[i] = v[i + 1] - 1;
cnt += diff;
}
}
cout << cnt;
return 0;
}
인증