[JAVA]2847 게임을 만든 동준이, 그리디, 실버4

 📚 문제  

2847번: 게임을 만든 동준이

🔍 아이디어  

먼저 한번 모든 입력을 받는다.

그 후에는 맨 뒤에서부터 i번째의 숫자가 i+1보다 적어도 1이상 작아야 한다는 조건으로 문제를 해결한다.

즉 arr[i] = arr[i+1]-1이어야 한다. 

 

1) 현재 arr[i] 숫자가 arr [ i+1]보다 크거나 같은 경우 (arr[i]>=arr[i+1]) :

arr [i] = arr[i+1]-1이어야 최소조건을 만족하기 때문에

sum에 arr[i]-arr[i+1]+1을 더하고 before을 arr[i+1]-1로 바꾼다.

 

2) 반대의 경우인 arr[i]<arr[i+1]의 경우라면 가능한 경우이므로 before값을 arr[i]로 교체한다.

📝 풀이 

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[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        int before = arr[n - 1];
        int sum = 0;
        for (int i = n - 2; 0 <= i; i--) {
            if (arr[i] >= before) {
                sum += (arr[i] - before + 1);
                before = before - 1;
            } else {
                before = arr[i];
            }
        }
        System.out.println(sum);
    }
}