글 읽기 - 틀렸습니다ㅠㅠ 도와주세요

aigorithm 4년 전 0

그리디 알고리즘과 원형 큐를 이용해서 구현을 해봤습니다..

끝나는 시간이 가장 빠른 회의를 골라주는것을 최적해라고 생각하고 풀었습니다.

끝나는 시간이 가장 빠른 값(compare_value)을 기준으로 그보다 일찍 시작하는 회의가 있으면 죄다 pop해주었습니다.

그 중에서 시작,끝 시간이 compare_value랑 같은 경우만 pop해주면서 count를 하나씩 더 해주었습니다.

이렇게 해서 제출했는데 틀렸다고 나오네요.

제가 어느 부분을 놓치고 있는걸까요 ㅠㅠ 다른 반례가 있는걸까요? 아님 알고리즘 자체를 잘못 짠걸까요..

#include <iostream>
#include <queue>
using namespace std;

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

int main() {

  int N, compare_value, temp, count = 0;
  Conf conf;
  queue<Conf> que;
  bool is_exist;

  cin >> N;

  for (int i = 0; i < N; i++) {
    cin >> conf.start >> conf.end;
    que.push(conf);
  }

  //큐가 빌 때까지
  while(!que.empty()){
    is_exist = false;
    compare_value = que.front().end;
    
    // 끝나는 시간이 가장 빠른 회의의 끝나는 시간을 compare_value로 저장한다.
    for (int i = 0; i < que.size(); i++) {
      if(que.front().end < compare_value){
        compare_value = que.front().end;
      }
      que.push(que.front());
      que.pop();
    }

    // compare_value보다 일찍 시작하는 회의들을 다 pop한다.
    temp = que.size();
    for (int i = 0; i < temp; i++) {
      if (que.front().start < compare_value) {
        if (que.front().end == compare_value) {
          is_exist = true;
        }
        que.pop();
      }
      else if(que.front().start == compare_value){
        que.pop();
        count++;
      }
      que.push(que.front());
      que.pop();
    }

    // 시작,끝시간이 같은 회의들만 있을때를 고려
    if (is_exist) {
      count++;
    }
  }
    
  cout << count;

  return 0;
}

skdty87 4년 전 3

반례입니다.

# Case 1
10
4 7
2 2
1 9
2 9
3 7
4 7
2 7
4 7
1 5
2 2

Answer: 3
Wrong Answer: 5

# Case 2
4
30 100
110 150
130 140
100 160

Answer: 2
Wrong Answer: 3

첨부한 코드 일부분에서 과연 저 조건에 해당하는 모든 경우에 count를 올려줘야 하는지 생각해 보세요.

else if(que.front().start == compare_value){
    que.pop();
    count++;
}

aigorithm 4년 전 0

정말 감사합니다!! ㅠㅠ 그 부분을 놓치고 있었네요

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

문제

문제

출처

ICPC

틀렸습니다ㅠㅠ 도와주세요

aigorithm 4년 전 0

skdty87 4년 전 3

aigorithm 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말