[C/C++] BOJ(백준) 2847 "게임을 만든 동준이" 문제 풀이 & 소스 코드

#문제정보

출처 : www.acmicpc.net/problem/2847

난이도 : 실버4

분류 : 그리디(GREEDY) 알고리즘

 

#문제분석

레벨별로 점수를 부여하기 위해서는, 각 레벨의 점수가 오름차 순으로 주어져야 합니다.

단, 점수를 내리는것을 최소한으로 해야 하기 때문에, i-1번째 레벨의 점수가 i번째 레벨의 점수보다 높은 점수를 갖고 있다면, i번째 레벨의 점수 - 1 값을 i-1번째 레벨에 부여하면 됩니다.

따라서 저는 레벨의 점수를 갖고 있는 level 벡터의 마지막 값을 compare 점수에 초기화 한 뒤 반복문을 돌려서 뒤에서부터 차례로 검사했습니다.

int compare = level[N-1];
	for (int i = N - 2 ; i >= 0 ; i--)
	{
		while (level[i] >= compare)
		{
			level[i]--;
			res++;
		}
		compare = level[i];
	}

 

#소스코드

#include <iostream>
#include <vector>
using namespace std;
vector<int> level;
int res;

int main()
{
	int N;
	cin >> N;
	for (int i = 0 ; i < N ; i++)
	{
		int temp;
		cin >> temp;
		level.push_back(temp);
	}
	
	int compare = level[N-1];
	for (int i = N - 2 ; i >= 0 ; i--)
	{
		while (level[i] >= compare)
		{
			level[i]--;
			res++;
		}
		compare = level[i];
	}
	cout << res;
	return 0;
}