글 읽기 - 19598 반례 찾아주십쇼!!!!

jminie 3년 전 0

어디가 틀렸는지 모르겠습니다.

문제에서 회의의 시작시간은 끝나는 시간보다 항상 같다고 해줬기 때문에 시작과 동시에 끝나는 회의는 없는거 같아서

코드가 맞는거같은데...

어디가 문제인지 혹은 반례가 있다면 찾아주시면 정말 감사하겠습니다.

n = int(input())

ar = []
for i in range(n):
    start, end = map(int, input().split())
    ar.append((start,end))

ar = sorted(ar, key = lambda x : x[1]) #끝나는 시간으로 오름차순 정리

endtime = ar[0][0]+1 #ar의 첫번째 시작시간보다 1을 더해줘 아래 for문의 첫번째 반복변수 i가 if문에서 실행되게 설정.
count = 0
for i in ar:
    if i[0] < endtime: #끝나는 시간과 시작시간이 같으면 동시에 다른회의가 시작할 수 있으므로 <= 가 아닌 <로 써줌
        endtime = i[1] # 끝나는 시간을 endtime에 저장
        count += 1 #다음 회의 시작시간이 전 회의 끝나는 시간보다 빠를 경우 회의실 count + 1
    else:
        endtime = i[1] #다음 회의 시작시간이 전 회의 끝나는시간과 같거나 늦을경우 회의실은 추가되지 않으나 
        continue       # 회의가 끝나는 시간은 그 다음 회의 끝나는 시간으로 업데이트됨.
print(count)
    

esotericjihun 3년 전 5

반례입니다!

3

0 10

5 20

15 25

(회의 #1, 회의 #3) / (회의 #2) 이렇게 묶으면 두 개의 회의실로 할 수 있습니다. 작성자 분께서 올려주신 코드는 3을 출력하므로 확인해보시면 좋을 것 같습니다!

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

문제

문제

출처

ICPC

19598 반례 찾아주십쇼!!!!

jminie 3년 전 0

esotericjihun 3년 전 5

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말