글 읽기 - 시간초과 질문있습니다.

khs0314 6년 전 0

파이썬으로 문제 푸는데, 1005번 시간초과를 도저히 해결 못해서 질문남깁니다.

이게 실제 연산량이 많은건지, 많다면 어디를 잘못 짠 건지, 아니면 특정 입력에 무한루프에라도 빠지는건지..

당췌 답을 알지를 못하겠습니다. 테스트에 사용하는 입력이라도 알면 수정을 하겠는데, 그것도 모르니 계속 발만 동동 구르네요.

문제는 한 단계 지나면 그때 최대값을 비교하여 저장하는 방식으로 풀었습니다.

import copy
a = int(input())
for X in range(a):
    b = input()
    c = input()    
    b = b.split()
    c = c.split()
    d = []
    c = [0]+c
    f = []
    g = []
    for y in range(len(c)):
        c[y] = int(c[y])
    f = copy.copy(c)
    for Y in range(int(b[1])):
        d = input()
        d = d.split()
        d[0] = int(d[0])
        d[1] = int(d[1])
        if d[0] != d[1]:
            g += [d]
    T = int(input())
    
    for Y in range(int(b[1])):
        if g ==[]:
            T=1
            break
        if T == g[Y][1]:
            while T == g[Y][1]:
                f[g[Y][1]] = max(f[g[Y][1]],f[g[Y][0]]+c[g[Y][1]])
                Y += 1
                if Y == int(b[1]):
                    break
            break
        if int(b[0]) ==1:
            T = 1
            break
        f[g[Y][1]] = max(f[g[Y][1]],f[g[Y][0]]+c[g[Y][1]])
    print(f[T])

djm03178 6년 전 0

제가 내공이 부족해서인지는 모르겠지만, 소스 코드를 도저히 이해할 수가 없습니다. 저도 쉬운 문제 풀 때는 귀찮아서 알파벳 하나로 변수명 짓기를 많이 하지만, 어려운 문제에서는 이렇게 하면 자신도 나중에 헷갈릴 뿐더러, 타인이 볼 때는 완전히 암호문이 됩니다.

질문을 하려면 최소한 자신의 코드가 어떤 알고리즘으로 동작하는 것인지, 그리고 어떤 변수와 함수가 무슨 역할을 하는 것인지 정도는 알 수 있게 해주셨으면 좋겠습니다.

jh05013 6년 전 1

일단 input -> sys.stdin.readline 으로 바꿔야 되긴 한데...

저도 Python3 쓰고있는데 이 문제에서 다른 쓸데없는 마이크로 최적화 아무리해도 시간초과가 떠서 며칠째 전전긍긍하다 jh05013님 댓글 보고 input을 sys.stdin.readline으로 바꾸니 그냥 통과되네요. 저는 위상정렬써서 풀었지만 다른분들 답들을 보니 굳이 위상정렬이 아니라도 되네요. 입력받는 방법만 바꾸시면 통과되든, 틀렸습니다가 뜨든 할겁니다.

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

문제

문제

출처

ICPC

시간초과 질문있습니다.

khs0314 6년 전 0

djm03178 6년 전 0

jh05013 6년 전 1

khris 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말