99클럽 코테 스터디 16일차 TIL(그리디)

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

제한조건

• 레벨의 점수를 감소시켜 레벨을 클리어할 때 주는 점수가 증가하게 만든다
• 점수는 20,000보다 작은 양의 정수이다.

🚨 오늘의 학습

⭐️그리디⭐️

🗝️ 레벨의 점수를 줄일 수 만 있다(늘리기 불가)

🗝️ 가장 마지막 레벨을 기준으로 이전 레벨의 점수를 줄여야 최소한의 방법을 구할 수 있다

오늘의 회고

• 첫번째 시도
  점수의 최소값과 마지막 레벨의 점수의 차이를 통해 시작 점수를 지정하고 1씩 증가된 다음 레벨의 점수를 설정하는 방법으로 구현하려고 했다
  하지만
  문제1) 최소값과 마지막 레벨의 점수가 같으면?
  문제2) 점수차이가 주어진 총 레벨보다 크면/작으면??
  점수차이: 8-2, 총 레벨: 5
  점수차이: 8-3, 총 레벨: 4

• 두번째 시도(성공)
  현재 레벨의 점수를 기준으로 작은 점수를 갖게 하는 것을 목표로 시도
  각 레벨에서 이전 레벨의 값을 비교하여 크거나 같으면 -1씩 줄여 나가기

package com.example.algorithm.Greedy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BJN_2847 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int result = 0;

        int trier = Integer.parseInt(st.nextToken());

        int[] points = new int[trier];

        for(int i=0; i<trier; i++){
            st = new StringTokenizer(br.readLine());
            points[i]=Integer.parseInt(st.nextToken());
        }

        for(int i=(trier-1); i>0; i--){
            if(points[i]<=points[i-1]){
                while(points[i]<=points[i-1]){
                    points[i-1]--;
                    result ++;
                }
            }
        }

        System.out.println(result);


    }

}