[백준] 2847번: 게임을 만든 동준이 (C언어)

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

2847번: 게임을 만든 동준이

 

 

 

 

레벨의 점수가 그 다음 레벨의 점수보다 더 낮도록 만들어야 한다

​

점수를 깎는 횟수가 최소가 되어야 하므로

 

맨 마지막 레벨의 게임(N번째 게임)부터 시작해 아래로 내려가면서 점수를 깎는 게 효율적이다

 

i - 1 번째 게임의 점수가 i 번째 게임의 점수보다 크거나 같으면 i 번째 게임의 점수보다 1 더 작아지도록 깎아준다

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

int main() {
	int N, i;
	scanf("%d", &N);
	int* score = (int*)malloc(sizeof(int) * N);
	int cnt = 0;	// 깎는 횟수
	for (i = 0; i < N; i++)
		scanf("%d", &score[i]);
	
	for (i = N - 1; i > 0; i--) {
		if (score[i - 1] >= score[i]) {	// 앞 레벨의 점수가 더 크거나 같으면
			cnt += score[i - 1] - score[i] + 1;	// 일단 최소로 깎는 횟수를 연산해 누적시킴
			score[i - 1] = score[i] - 1;	// 점수를 깎아줌
		}
	}
	printf("%d", cnt);
	free(score);
	return 0;
}