백준 - 2847

문제링크

문제요약

문제의 요구 사항은 다음과 같다.

• 레벨 점수가 배열로 주어진다.
• 각 레벨의 점수는 다음 레벨보다 작아야한다.
• 점수를 수정하는 동작은 1번동작할때 1점씩 감소한다.
• 수정동작을 최소한으로 해야한다.

즉, 점수 배열을 오름차순으로 정렬하기 위해서 수정동작을 거쳐야하는데 이때 이 수정동작을 최소로 하는 경우의 수를 요구는 문제이다.

풀이

이 문제는 그리디문제이다. 명제를 세우고 명제가 맞는지 확인하고 맞다면 그대로 풀면된다.

 

명제
레벨의 점수를 뒤에서부터 순차적으로 비교하며, 현재 레벨의 점수가 다음 레벨의 점수 이상인 경우, 최소한으로 점수를 낮추어 조건을 만족시키면 전체 최소 감소 횟수를 보장할 수 있다.

---

소스코드

#include <iostream>
using namespace std;

/*
레벨을 난이도 순으로 배치했지만 잘못된 점수가있음
점수는 감소만 시킬 수 있다.
지금 점수주는것이 순서대로 배치가안되어있으니 어디를 감소시켜야할까
5 5 5 -> 4 5 5 -> 4 4 5 -> 3 4 5
*/

int n;
int board[105];
int cnt;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> board[i];
        }
    for (int i = n - 1; i > 0; i--) {
        while (board[i] <= board[i - 1]) {
            board[i - 1] -= 1;
            cnt++;
        }
    }
    cout << cnt;
}