글 읽기 - 파이썬 3%대 시간초과

xorms86 4년 전 0

알고리즘 초보입니다.

시간초과가 나는데 sorted에서 나는건지 이중 for문에서 나는건지 모르겠습니다.

틀리는 입력도 있을수 있으니 틀릴만한 입력도 알려주시면 감사합니다.

n=int(input())
arr=[]
result=[]

for i in range(n):
    a,b = map(int,input().split())
    arr.append((a,b))

arr=sorted(arr)
    
for i in range(n):
    count=1
    t=arr[i][1]
    for j in range(i+1,n):
        if arr[j][0]>=t:
            t=arr[j][1]
            count+=1
    result.append(count)
            
print(max(result))
    
            

jintak0401 4년 전 0

그리디 알고리즘을 아시나요? 혹시 모르신다면 공부하시고 이 문제 다시 보시면 푸실 수 있으실거에요

wider93 4년 전 0

사실 작성하신 풀이 자체가 완전탐색이 아니기 때문에 그리디라고 볼 수 있습니다. 다만 잘못된 그리디 방법을 쓰고 계십니다.

회의를 겹치지 않게 최대한 많이 우겨넣기 위해 무엇을 기준으로 정렬하면 좋을지 다시 고려해 보시는 게 좋을 것 같습니다.

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

문제

문제

출처

ICPC

파이썬 3%대 시간초과

xorms86 4년 전 0

jintak0401 4년 전 0

wider93 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말