[프로그래머스] 181188: 요격 시스템

url : https://school.programmers.co.kr/learn/courses/30/lessons/181188

프로그래머스

 

문제가 그리디인 이유

요격하는데 필요한 최소한의 미사일 갯수

=> 매 순간 최소의 미사일 개수를 선택하고, 그것을 계속하면 전체적인 최소 미사일 개수가 나온다 (=최적 부분 구조)

✅ 구간이 나오고, 정렬 가능하다면 그리디를 생각하기!

 

그리디 중 구간 스케줄링

1. sort(끝점 기준 정렬)

2. 기준값이 시작값보다 작으면 cnt++

 

코드

#include <bits/stdc++.h>

using namespace std;
// 끝점 기준으로 오름차순 정렬
bool cmp(vector<int> v1, vector<int> v2){
    return v1[1] < v2[1];
}

int solution(vector<vector<int>> targets) {
    int answer = 0;
    //1. 끝점 기준으로 정렬하기
    sort(targets.begin(), targets.end(), cmp);
    //2. 시작점이 요격 위치보다 큰 경우에 미사일 발사
    double lastIntercept=-1;
    for(vector<int> target:targets){
        if(lastIntercept<target[0]){
            lastIntercept = target[1]-0.1;
            answer++;
        }
    }
    //3. 정답 출력
    return answer;
}