[TIL] 99클럽 코테 스터디 16일차 TIL + 백준 2847 게임을 만든 동준이

문제 풀이

 

문제 탐색하기

이 문제는 그리디 알고리즘을 활용하여 풀 수 있습니다. 우선 맨 마지막 레벨을 클리어 했을 때 얻는 점수보다 그 앞 레벨을 클리어했을 때 얻을 수 있는 점수는 낮아야합니다. 현재의 레벨과 그 앞의 레벨을 비교하면서 앞의 레벨에서 얻을 수 있는 점수가 현재 레벨에서 얻을 수 있는 점수보다 높을 때 얻을 수 있는 점수를 현재 레벨의 점수보다 1 낮게 감소시킵니다. 이를 반복하면서 총 감소시키는 점수를 카운트 하게되면 답을 구할 수 있습니다.

 

 

문제 풀이

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        ArrayList<Integer> list = new ArrayList<>();
        for(int i=0; i<N; i++){
            list.add(Integer.parseInt(br.readLine()));
        }

        int minusScore = 0;
        for(int i=list.size()-1; i>=1; i--){
            int a = list.get(i);
            int b = list.get(i-1);

            if(a <= b){
                minusScore += b-a+1;
                b = a-1;
                list.add(i-1, b);
            }
        }

        System.out.println(minusScore);
    }
}