글 읽기 - 시간초가가 나옴니다

andrewpark05 2년 전 0

프로그램을 만들었는데, 시간 초과가 나옴니다

시간초과 해결하는 것좀 도와주세요..

그리고 이 문제를 이렇게 접근하는게 맞나요?

N=int(input())
A=[[0,0] for i in range(N)]
B=[]
C=[]
for i in range(N):
    task=input().split()
    A[i][0]=int(task[0])
    A[i][1]=int(task[1])
    if not A[i][0] in B:
        B.append(A[i][0])
    if not A[i][1] in B:
        B.append(A[i][1])
B.sort()
for i in range(max(B)+1):
    D=[]
    if i==0:
        C.append(0)
    else:
        for j in range(N):
            a=-1
            if A[j][0]==i:
                a=A[j][1]
            elif A[j][1]==i:
                a=A[j][0]
            if i>a and a>-1:
                D.append(C[a]+1)
        if D!=[]:
            D.append(C[i-1])
            C.append(max(D))
        else:
            C.append(C[i-1])
print(C[len(C)-1])

henyu16 2년 전 1

N이 10만 까지 가능해서 이중 for문 쓰셔서 10만^2번 계산해서 시간 초과 뜬 거 같습니다.

힌트는 리스트 A를 시작 시간을 오름차순으로 정렬하고 만약 시작시간이 같다면 끝나는 시간 오름차순으로 정렬후 판단해주면 됩니다.

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

문제

문제

출처

ICPC

시간초가가 나옴니다

andrewpark05 2년 전 0

henyu16 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말