글 읽기 - 그리디로 풀 때 틀린 곳...ㅠㅠㅠㅠㅠ 제발 도와주세요 너무 슬픕니다ㅠㅠㅠ

hyeyoung0112 4년 전 0

UCPC 풀이 보고 greedy로 풀어보려고 하는데 자꾸 틀려서 너무 슬픕니다...

guard[]에 형섭이보다 잘하는 K-1명이 마지막으로 참여한 대회가 끝나는 날을 저장하고, 항상 내림차 순으로 저장되어 있게 했습니다. HS에는 형섭이가 마지막으로 참여한 대회의 날짜를 기억하게 했습니다.

대회들을 끝나는 날짜 순서대로 오름차로 정렬하고, 그 순서대로 형섭이가 참여할 수 있는지 확인하게 했습니다. 형섭이가 참여할 수 있는 경우 K-1명이 형섭이의 우승을 막을 수 있는지를 insertGuard 함수 안에서 검사하고, 막을 수 있는 경우 guard[]를 수정했습니다. 형섭이가 우승할 수 있는 경우 wins를 늘리고 형섭이가 마지막으로 참여한 대회의 날짜를 수정했습니다.

K-1명중 제일 늦게 끝나는 대회에 참여한 사람이 막게하는 거까지 했는데 왜 안되는 걸까요...

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <bits/stdc++.h>

#define MAX 100000

using namespace std;

typedef struct Date {
        int start;
        int end;
}Date;

int N, K;
Date contests[MAX];
int HS;
int guard[MAX];

bool asc(Date a, Date b){
        return a.end < b.end;
}

bool insertGuard(int startDate, int endDate) {
        // K-1명이 막을 수 없음
        if (guard[K-2] >= startDate) return false;

        // 막을 수 있는 사람 중 가장 늦게 끝나는 대회에 참여한 사람을 고른다
        int index = upper_bound(guard, guard+K-2, startDate, greater<int>()) - guard;
        guard[index] = endDate;
        while (index > 0 && guard[index-1] < guard[index]) {
                int tmp = guard[index];
                guard[index] = guard[index-1];
                guard[index-1] = tmp;
                index--;
        }
        return true;
}

int main(){
        scanf("%d %d", &N, &K);
        for (int i=0; i<N; i++) {
                scanf("%d %d", &contests[i].start, &contests[i].end);
        }

        sort(contests, contests + N, asc);
        
        // 값 초기화
        for (int i=0; i<K-1; i++) guard[i] = 0;
        HS = 0;
        int wins = 0;
        for (int i=0; i<N; i++) {
                int start = contests[i].start;
                int end = contests[i].end;
                //형섭이 참가 가능
                if (start > HS) {
                        bool result = insertGuard(start, end);
                        //K-1명이 방해 불가능
                        if (!result) {
                                HS = end;
                                wins++;
                        }
                }
        }

        printf("%d\n", wins);
        return 0;
}

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

문제

문제

출처

ICPC

그리디로 풀 때 틀린 곳...ㅠㅠㅠㅠㅠ 제발 도와주세요 너무 슬픕니다ㅠㅠㅠ

hyeyoung0112 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말