Backjoon_2847_그리디_

생각할 겨를 없이 손이 가는쉬운 문제였지만,
색다르게 풀어보려고 했다.

가장 마지막 레벨에 있는 점수가 기준이 되고 , 그 점수부터 레벨이 하나 낮아질 때마다 1점씩 뺀 배열과 기존 배열과의 차이를 다 더하면 되지 않을까 했다.

예제

4 | 5 3 7 5 <- 기존 배열
4 | 2 3 4 5 <- 가장마지막 점수를 기준으로 1을 뺀 배열을 새로 만듬
(5-2) + (3-3) + (7-4) + (5-5) = 6

또다른 예제

5 | 5 5 5 5 5 <-기존
5 | 1 2 3 4 5
(5-1) + ... (5-0) = 10

또또다른 예제

5 | 17 12 25 16 18
5 | 14 15 16 17 18
|17-14| + |12-15| + |25-16| + |16-17| + |18-18| = 16

꽤나 신박한 방법이라 부대에서 막사로 복귀하고 연등하기만을 기다렸지만,
반례를 생각하지 못했다.

17 12 25 16 18 과 17 12 25 16 1888 은 비슷한 형태지만,
위에 방식으로 계산했을 경우 의도하지 않은 큰 값이 나와버린다.

그래서 그냥 정석으로 했다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
	int n,T;
	cin >> n;
	T = n;
	int m_cnt = 0;
	vector<int> score;
	
	while (T--)
	{
		int a;
		cin >> a;
		score.push_back(a);
	}
	
	for (int j=n-2;j>=0;j--)
	{
		for (int i = n - 1; i > j; i--)
		{
			if (score[j] >= score[i])
			{
				m_cnt += score[j] - score[i] + 1;
				score[j] = score[i] - 1;
			}
		}
	}
	cout << m_cnt;
	return 0;
}