글 읽기 - 그리디 접근 방식 관련하여 질문이 있습니다.

neogate 2년 전 0

문제를 다른 방식으로 접근하여 맞추긴 했습니다만 아래와 같은 풀이방식이 틀리는 이유를 모르겠습니다.

주석에 쓰인대로 들어온 구간들을 구간의 길이에 대해 오름차순으로 정렬하여 주고 길이가 같다면
시작 위치에 대하여 오름차순 정렬을 진행하였습니다

그 이후 lower_bound로 남아있는 책들중 조건을 만족하는 가장 낮은 번호를 가진 책을 배정해주었는데 왜 이 풀이가 틀리는지 궁금합니다.

// 정렬 순서 => 1.구간의 길이 2. 구간의 시작 위치
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int t,n,m,a,b;
vector<pair<int,int>>v;
set<int>book;
bool cmp(pair<int,int>a, pair<int,int>b){
  if(a.second-a.first==b.second-b.first)
    return a.first<b.first;
  else 
    return a.second-a.first<b.second-b.first;
}
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin>>t;
  for(int asdf=0;asdf<t;asdf++){
    v.clear();
    v.shrink_to_fit();
    book.clear();
    int ans=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)book.insert(i);
    for(int qwer=0;qwer<m;qwer++){
      cin>>a>>b;
      v.push_back({a,b});
    }
    sort(v.begin(),v.end(),cmp);
    for(auto i:v){
      auto it=book.lower_bound(i.first);
      if(it==book.end()||*it>i.second)continue;
      else{
        ans++;
        book.erase(*it);
      }
    }
    cout<<ans<<endl;
  }
}

dk10211 2년 전 1

반례 드립니다

1
6 6
1 5
1 2
2 3
3 4
4 5
5 6

틀리는 이유는 이 상황에서 6번 책을 사용하지 않았기 때문입니다

neogate 2년 전 0

아 그렇네요 지적 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

그리디 접근 방식 관련하여 질문이 있습니다.

neogate 2년 전 0

dk10211 2년 전 1

neogate 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말