Greedy 접근법 - 백준 14659번

위 문제에 대해 설정한 알고리즘은 다음과 같다.

기본적으로 왼쪽에서 오른쪽으로만 진행되기 때문에, 만약 기준점으로부터 오른쪽의 봉우리의 높이가 현재의 봉우리보다 낮다면, 그 봉우리의 용은 무조건 최고 활잡이가 될 수 없다. 따라서 오른쪽으로 진행하면서 자신보다 높은 봉우리가 등장했을때만을 고려해주면 된다. 

1) 오른쪽으로 진행하면서 (index값을 1씩 증가시켜주면서) 더 높은 봉우리가 나왔을 때 max과 처치한 적의 수를 업데이트해준다. 

2) 최고 활잡이를 가리기 위해서는 각각의 max 봉우리들의 적처치수를 비교해야하기 때문에 업데이트 하기 전에, 이전에 처치한 적의 수 중에서 가장 큰 적 처치 수를 result에 저장해둔다.  (result는 즉 가장 많이 처치된 적의 수) 

3) 마지막 봉우리까지 위의 과정을 반복한뒤, 마지막으로 result와 현재 봉우리의 적 처치수를 비교해준다. 

4) result값을 출력해준다. 

 

실제 코드는 아래와 같다. 

 

import java.util.Scanner;
 
public class hanzo {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt(); //num = 봉우리의 수이자 활잡이의 수
        int max,count,result;
        count=0; result = 0;
        
        int mountain[] = new int[num]; //입력된 봉우리의 높이를 저장할 배열 mountain
        for(int i = 0; i<mountain.length; i++) { //봉우리의 높이를 입력받는다. 
            mountain[i]=scanner.nextInt();        
        }
        
        max = mountain[0]; // 첫번째 봉우리의 높이를 max의 초기값으로 설정해준다. 
        
        for(int i=0; i<num; i++) { 
            if(max<=mountain[i]) { // 만약 현재의 봉우리보다 더 높은 봉우리가 나오면 
                max = mountain[i]; // max(현 시점에서 가장 높은 봉우리의 높이)값을 update해주고
                result = Math.max(result,count); // 현재까지 처치한 적의 수와, 이전에 가장 많이 처치한 적의 수를 비교하여서 더 큰 값을 result에 저장해준다. 
                count = 0; //다시 현재 처치한 적의 수를 0으로 update해준다. 
            }
            else count++; // 더 높은 봉우리가 나오기 전까지는 계속 처치한 적들의 수를 추가해주면서 반복을 진행한다. 
            
        }
        
        result = Math.max(result, count); // 마지막 최고 봉우리의 적 처치 수와 최고 처치 적의 수를 비교하여 더 큰 값이 결과값이 된다. 
        System.out.println(result); // 최대 처치 적의 수를 출력해준다. 
         
    }
 
}