글 읽기 - 파이썬 시간초과가 왜나는걸까요...??

epfzja 3년 전 0

코딩한거 봐주세요.. 이방법이 효율적이라 생각했는데 아닌가봐요..

어떻게 고쳐야할까요?

timetable = [] # 입력한 시간표
start_point = [] # 각 수업의 시작시간
study_time = [] # 각 수업시간
count = 0 # 중첩판정
cnt = [] # 중첩횟수

test_case = int(input())
for i in range(test_case):
    timetable.append(list(map(int, input().split())))
timetable.sort()


for i in range(test_case):
    start_point.append(timetable[i][0])
for i in range(test_case):
    study_time.append(timetable[i][1] - timetable[i][0])
    
    
for i in range(test_case): # 대상
    for j in range(test_case): # 비교군
        if i > j:
            if start_point[i] < (start_point[j] + study_time[j]):
                count += 1
        elif i < j:
            if (start_point[i] + study_time[i]) > start_point[j]:
                count += 1
    cnt.append(count)
    count=0
    
    
print(max(cnt))

shg9411 3년 전 1

N이 최대 20만이기에 O(N^2)의 방법으로는 불가능합니다.

정렬하신것을 이용해보세요.

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

문제

문제

출처

ICPC

파이썬 시간초과가 왜나는걸까요...??

epfzja 3년 전 0

shg9411 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말