백준 9576번 책 나눠주기

문제 링크입니다: https://www.acmicpc.net/problem/9576

이분매칭으로 푼 사람들이 더 많지만 저는 그리디하게 접근해서 풀었습니다.

b를 기준으로 오름차순 정렬을 한 상태에서 책을 나눠주면 풀리는 문제였습니다.

그리디 문제들은 사실 그리디하게 풀 수 있는 근거가 있어야하지만 왜 이렇게 풀어야하는지는 증명하지 못하겠습니다.

혹시 이렇게 풀어도 되는 이유를 아신다면 댓글 남겨주신다면 정말 감사하겠습니다.

#include <iostream>

#include <algorithm>

#include <vector>

#include <cstring>

using namespace std;

 

const int MAX = 1000 + 1;

 

bool visited[MAX];

 

bool cmp(pair<int, int> a, pair<int, int> b)

{

        if (!(a.second == b.second))

                 return a.second < b.second;

       

        return a.first < b.first;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int T;

        cin >> T;

 

        for (int t = 0; t < T; t++)

        {

                 memset(visited, false, sizeof(visited));

                 int N, M;

                 cin >> N >> M;

 

                 vector<pair<int, int>> v;

                 for (int i = 0; i < M; i++)

                 {

                         int a, b;

                         cin >> a >> b;

 

                         v.push_back({ a, b });

                 }

 

                 //b번을 기준으로 오름차순 정렬

                 sort(v.begin(), v.end(), cmp);

                 int result = 0;

                 for(int i=0; i<M; i++)

                         for(int j=v[i].first; j<=v[i].second; j++)

                                 if (!visited[j])

                                 {

                                          visited[j] = true;

                                          result++;

                                          break;

                                 }

 

                 cout << result << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~