Greedy 접근법 - 백준 2847

Greedy접근법의 또 다른 예시문제인 백준 2847번을 풀어봤다. 

최소 감소횟수를 구하는 것이기 때문에, 가장 마지막 레벨의 점수를 기준으로 잡고 문제를 풀어갔다. 

알고리즘을 다음과 같이 설정하여 접근하였다. 

1) 마지막 레벨의 점수를 max로 설정한다. 

2) 마지막 레벨부터 처음레벨로 거슬러올라가면서, 순차적으로 감소시켜준다.

-  초기 result값을 max-1로 설정

- 단계가 진행됨에 따라 result값을 update

3) 감소가 진행된다면 count(감소횟수를 기록하는 변수)를 update 시켜준다.  

 

실제 코드는 아래와 같다. 

 

import java.util.Scanner;
 
public class game {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scanner = new Scanner(System.in);
        int level_num = scanner.nextInt(); // 몇개의 레벨로 구성되어있는지 입력받는다. 
        int score[] = new int[level_num];
        
        for(int i=0; i<level_num; i++) { // 각 레벨별 점수를 입력받는다. 
            score[i] = scanner.nextInt();
        }
        
        int max= score[level_num-1]; // 가장 마지막 레벨의 점수가 가장 커야한다. 
        int result = max -1; // result는 max값에서 1을 빼준다. (가장 마지막 레벨의 점수보다 작아야하기 때문에) 
        int count = 0; // 감소한 횟수를 기혹해줄 변수 count
        
        for(int j=level_num-2; j>-1; j--) { // 가장 마지막 레벨의 점수는 그대로 두고, 그 점수를 기준으로 수열을 오름차순으로 정리해준다. 
            if(score[j]>result) { //score[j]와 result를 비교해서 만약 score[j]가 result(직전 레벨의 점수 -1)보다 크다면
                count = count + (score[j]-result); // 감소된 횟수를 세준다. 
                score[j] = Math.min(score[j], result); // score [j]의 값을 result값으로 설정해준다. 
                result = score[j]-1; // 다음비교를 위해서 result값을 update해준다. 
                
            }
            //score[j]가 result보다 작거나 같다면, result의 값을 1만 감소시키고 다음 반복으로 넘어간다. (최소감소횟수를 구하는 것임으로 -1만 해주면 된다.)
            else result = score[j] -1; 
        }
        
        System.out.println(count); // 감소된 횟수를 출력해준다. 
        
 
    }
 
}