99클럽 코테 스터디 16일차 TIL 그리디(게임을 만든 동준이)

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

<아이디어>

점수를 최소한으로 내려서 레벨점수를 증가하게 만들어야 하는 문제이다.

이 경우 뒤에서부터 순차적으로 탐색하는 경우 최소한으로 만들 수 있다.

뒤 점수보다 앞 점수가 같거나 크면 뒤 점수보다 1만큼만 작게 만들어줄 때 최소한으로 점수를 감소시키면 된다.

** 1감소가 1점이므로 절댓값으로 계산해주어야 한다

 

<제출 코드>

package STUDY.Week03;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Day16_BOJ_2847_게임을만든동준이 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        for(int i=0; i<n; i++) arr[i] = Integer.parseInt(br.readLine());
        int cnt = 0;
        for(int i=n-1; i>0; i--){
           // 앞 점수가 뒤 점수보다 크거나 같으면 뒤 점수보다 1 작게 만들어 줌
            if(arr[i-1] >= arr[i]){
                int tmp = Math.abs(arr[i-1] - arr[i] + 1);
                cnt += tmp;
                arr[i-1] -= tmp;
            }
        }
        System.out.println(cnt);
    }
}