[백준] 2847 게임을 만든 동준이 - Greedy / Java

• 문제 링크

2847번: 게임을 만든 동준이

 

• 풀이 과정

특정 레벨의 점수를 감소만 시켜 조정하므로 마지막 레벨의 점수가 가장 크다.

따라서 반복문을 역으로 돌려 마지막 레벨부터 확인한다.

 

만약 n = 1 일 경우 감소시킬 레벨이 없으므로 0 을 반환하고

그 외의 경우 입력을 크기가 n인 배열에 역순으로 저장한다.

 

만약 현재 레벨의 점수가 한 단계 상위 레벨보다 클 경우,

현재 레벨의 점수를 상위 레벨의 점수 - 1 로 조정할 수 있는 값을 구한다.

해당 값을 cnt 변수에 더하고, 현재 점수에는 빼어 점수를 최소한으로 조정한다.

 

이러한 과정을 거쳐 누적된 cnt 가 최소한의 점수 조정값이며 이를 정답으로써 출력한다.

 

• 풀이 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        if (n == 1)
            bw.write("0");
        else {
            int[] score = new int[n];
            for (int i = n - 1; i >= 0; i--)
                score[i] = Integer.parseInt(br.readLine());

            int cnt = 0;
            for (int i = 1; i < n; i++) {
                if (score[i] >= score[i - 1]) {
                    int adjust = score[i] - score[i - 1] + 1;
                    cnt += adjust;
                    score[i] -= adjust;
                }
            }

            bw.write(String.valueOf(cnt));
        }

        bw.flush();
    }

}