[Baekjoon] 2847 - 게임을 만든 동준이

📝 문제

 

 

🔑 풀이 과정

· 입력받은 레벨의 점수를 적당하게 감소시켜서 오름차순으로 만들어 주면 되는 문제.

즉, 배열의 요소를 다음 인덱스가 가리키는 요소보다 작게 만들면 되는 것

 

· 배열을 뒤부터 순회하면서, 현재 가리키는 인덱스가 i라면, 인덱스 i+1이 가리키는 요소보다 i가 가리키는 요소를 작게 만들면 된다. 나는 while문을 사용해서 이를 구현했다.

 

· 가장 최소한으로 내리는 방법을 구해야 하므로, 작아지면 바로 다음순서로 넘어간다.

(4 5 5 가 있으면 3 4 5 로 만드는게 최소, 굳이 2 4 5, 1 2 3 이런식으로 만들 필요가 없음)

 

 

 

🔓 답안

import java.io.*;

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()); //레벨의 수 입력받기
        int[] arr = new int[N];

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

        int count = 0;
        for(int i = N-2; i >= 0; i--){
            while(arr[i+1] <= arr[i]){
                arr[i]--;
                count++;
            }
        }

        bw.write(count + "\n");
        bw.flush();
        bw.close();
    }

}

- arr[i+1] > arr[i]가 되면 while문이 돌지 않고, 다음 순서의 for문으로 넘어가게 된다.

 

 

🖤 알고리즘 분류

- 그리디 알고리즘