글 읽기 - C++ 반례가 있는지 질문드립니다 (deque 사용)

ympark99 2년 전 0

테스트 코드나 다른 값을 입력해봐도 일치하는데 틀렸습니다가 뜹니다.. 혹시 반례가 있을까요?

감사합니다.

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

bool comp(pair<int, int> &a, pair<int, int> &b){
    if(a.first == b.first) return a.second < b.second;
    return a.first < b.first;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL);

    deque<pair<int, int>> dq;

    int n;
    cin >> n;

    vector<int> v;

    while(n--){
        int s, t;
        cin >> s >> t;
        dq.push_back(make_pair(s, t));
    }
    
    sort(dq.begin(), dq.end(), comp);

    int answer = 0;
    int cnt = 0;
    while(!dq.empty()){
        int i = 0;
        while(i < dq.size()){
            if(v.empty()){
                v.push_back(dq.front().second);
                answer++;
                dq.pop_front();
                continue;
            }
            if(dq[i].first >= v.back()){
                v.push_back(dq[i].second);
                dq.pop_front();
            }
            else i++;           
        }
        v.clear();
    }
    cout << answer;
}

bearsff 2년 전 0

반례입니다

5
1 7
2 3
3 4
4 8
7 10

답: 2
오답: 3

if(dq[i].first >= v.back()){
v.push_back(dq[i].second);
dq.pop_front();
}

이 부분에서 오류가 있는 것 같습니다. 값을 가져오는 곳으 dq에서 i번째의 값을 가져오는데 pop_front는 pop을 앞에서 합니다. 이렇게 되면 강의들 목록을 저장하신 덱에서 벡터에 넣어준 적절한 강의(i번째강의)를 아닌 가장 앞에 있는 강의를 삭제하게 됩니다. 아마 그래서 이 부분에서 오류가 날듯합니다.

ympark99 2년 전 0

상세한 답변 감사합니다!! 덕분에 문제 부분을 바로 파악했습니다. :)

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

문제

문제

출처

ICPC

C++ 반례가 있는지 질문드립니다 (deque 사용)

ympark99 2년 전 0

bearsff 2년 전 0

ympark99 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말