2847 게임을 만든 동준이(C++)

https://www.acmicpc.net/problem/2847

동준이라는 분이 게임을 만들었는데

갓겜이라 낮은 구간의 점수가 높은 구간의 레벨보다 점수가 높다고한다

이를 패치를 통해서 낮은 구간의 점수를 너프때리는 문제

1. 문제

---

간단 설명

첫째 줄에 레벨의 수 N

다음 N개 줄부터는 각 레벨을 클리어하는 점수가 주어진다

3 5 5 5가 주어지면 3개의 레벨이 존재하고, 1레벨 5점, 2레벨 5점, 3레벨 5점이라는 뜻이다

5 5 5를 3 4 5로 만드는것이 패치의 목표

1만큼 감소시키는 것이 1번이므로, 1레벨은 2번, 2레벨은 1번 너프해서

총 3번이 예제 1번의 답이 된다

2. 문제 분석

---

필요변수

• 레벨의 개수 int N (1 ≤ N ≤ 100)

• 점수를 저장할 벡터 vector<int> level (점수는 20,000보다 작은 양의 정수)

• 몇번 감소했는지 저장할 int cnt

알고리즘

1. N을 입력받고, level들의 점수를 입력받는다
2. 맨 뒤의 원소 i 부터 1번 원소까지(0까지있음 C++기준) 그 앞 원소 i-1과 비교한다
    2-1. 만약 i-1원소가 i보다 크다면, i-1을 너프한다
    2-2. 두 원소의 차이를 구하고, 그 차이만큼 빼준다
    2-3. 뺴준 만큼 cnt에 추가해준다
3. cnt 출력 후 종료

3. 소스코드

---

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

using namespace std;

int N;
vector<int> level;
int cnt = 0;

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N;
	level.resize(N);
	for (int i = 0; i < N; i++)
		cin >> level[i];

	// 맨 뒤 원소값과 그 앞 원소를 비교
	for (int i = N - 1; i >= 1; i--) {
		// 앞 원소가 뒤 원소보다 크다면, 그 차이만큼 빼주고 뺀 만큼 cnt를 증가시킴
		if (level[i - 1] >= level[i]) {
			int diff = level[i - 1] - level[i];
			level[i - 1] -= diff + 1;
			cnt += diff + 1;
		}
        /*
        while (level[i - 1] >= level[i]) {
			level[i - 1]--;
			cnt++;
		}
        얘랑 같으나 한방에 차이만큼 빼서 시간복잡도를 줄임
        */
	}

	cout << cnt;

	return 0;
}