[99클럽/코딩테스트 챌린지/C++]게임 레벨 점수를 최소한으로 감소시켜 순서대로 증가시키기

문제 링크 : 

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

 

문제 설명

동준이가 만든 게임에는 여러 레벨이 있고, 각 레벨을 클리어할 때 점수를 얻는다. 이 점수는 레벨이 높아질수록 커져야 하지만, 현재는 쉬운 레벨의 점수가 어려운 레벨보다 높은 경우가 존재한다. 이를 해결하기 위해 각 레벨의 점수를 감소시켜야 하며, 이때 최소한의 감소 횟수로 점수를 조정하는 것이 목표다.

접근법

이 문제는 그리디 알고리즘을 사용하여 해결할 수 있다. 가장 높은 레벨부터 점검하며, 현재 레벨 점수가 이전 레벨보다 낮거나 같을 경우 이전 레벨의 점수를 현재 레벨보다 1 낮게 만든다. 이 과정을 반복하면서 각 레벨의 점수를 점진적으로 감소시키며, 필요할 때마다 감소 횟수를 누적하여 최종 답을 도출한다.

#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <math.h>
#include <map>
#include <queue>

using namespace std;

int main() {
	int N = 0;

	std::cin >> N; 
	vector<int> levels(N);
	for (size_t i = 0; i < N; i++)
	{
		std::cin >> levels[i];
	}
	
	int count = 0;
	for (size_t i = levels.size() - 1; i > 0; i--) {
		while (levels[i] <= levels[i - 1])
		{
			levels[i - 1]--;
			count++;
		}
	}
	std::cout << count << '\n';
	return 0;
}

코드 설명

1. 데이터 입력: 각 레벨의 점수를 벡터에 저장한다.
2. 감소 작업 수행: 가장 높은 레벨부터 시작하여, 점수를 확인하면서 이전 레벨의 점수가 현재 레벨 점수보다 크거나 같을 경우 점수를 감소시킨다.
3. 결과 출력: 총 감소 횟수를 출력한다.

배운 점

이 문제를 통해 그리디 알고리즘을 활용하여 역방향으로 접근하는 방식이 유효한 경우를 배웠다. 이와 같이, 높은 레벨부터 감소를 진행하는 방식이 문제의 최적 해법임을 깨달았다.

결론

이 문제는 그리디 알고리즘으로 각 레벨 점수가 증가하도록 조정하는 것이 핵심이었다. 필요할 때마다 점수를 최소로 감소시키며 문제를 해결할 수 있었고, 앞으로도 유사한 문제에서 그리디 접근법을 효과적으로 적용할 수 있을 것이다.