백준 2847번 ) 게임을 만든 동준이 (java)

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

2847번: 게임을 만든 동준이

 

문제

 

풀이

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

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());
        int count = 0;
        int[] score = new int[N];

        for(int i=0; i<N; i++){
            score[i] = Integer.parseInt(br.readLine());
        }

        for(int i=N-2; i>=0; i--){
            if(score[i]>=score[i+1]){
                count += (score[i]-score[i+1]+1);
                score[i] = score[i+1]-1;
            }
        }

        System.out.println(count);
    }
    
}

 

이 문제의 키포인트는 '점수를 내리는 것을 최소한으로 하는것' 이므로, 한단계 더 높은 레벨보다 1만큼만 작은 수를 만들면 된다.

그리디 알고리즘 문제였는데, 사실 그냥 배열을 위에서부터 탐색하면서 최소한으로 줄여나가고, 줄인만큼 답으로 카운트하면 되는 문제였다.

 

코드가 어렵지는 않지만, 문제를 봤을 때 어떻게 구현해야하는지 떠올리는 방법에 익숙해지자!