글 읽기 - 반례를 알고 싶습니다(그리디)

ledi000 3년 전 1

그리디로 풀었고, b(아래 코드에서 end에 해당)를 기준으로 오름차순 정렬하여 풀었는데,

아무리 풀어도 50%에서 틀렸다는 결과가 나옵니다.

게시판 내에 있는 모든 반례를 적용해 보았지만 값이 잘 나와서 틀린 곳이 어딘지 모르겠네요...

반례 혹은 틀린 부분 제시해 주신다면 정말 감사하겠습니다..ㅜㅜ

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define MAX 1000
using namespace std;
typedef pair<int, int> pii;
int T, N, M;
bool isUsed[MAX + 1];
void init() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(0);
}

bool compare(pii num1, pii num2) {
    if (num1.second == num2.second) return num1.first < num2.first;
    return num1.second < num2.second;
}

int countMaxStudents(vector<pii> nums) {
    int cnt = 0;
    sort(nums.begin(), nums.end(), compare);
    for (int idx = 0; idx < M; idx++) {
        int start = nums[idx].first;
        int end = nums[idx].second;
        for (int num = start; num <= end; num++) {
            if (!isUsed[num]) {
                isUsed[num] = true;
                cnt++;
                break;
            }
        }
    }
    return cnt;
}

int main() {
    init();
    cin >> T;
    while (T--) {
        cin >> N >> M;
        memset(isUsed, 0, sizeof(isUsed));
        vector<pii> nums;
        for (int idx = 0; idx < M; idx++) {
            int start, end;
            cin >> start >> end;
            nums.push_back(pii(start, end));
        }
        int ans = countMaxStudents(nums);
        cout << ans;
    }
    return 0;
}

djm03178 3년 전 0

매 케이스마다 개행 문자를 출력해야 합니다.

ledi000 3년 전 0

앗..... 답변 정말 감사합니다!

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

문제

문제

출처

ICPC

반례를 알고 싶습니다(그리디)

ledi000 3년 전 1

djm03178 3년 전 0

ledi000 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말