글 읽기 - [파이썬] 99%성공 후 시간초과

thdehdx 3년 전 0

min 대신 for 문으로 탐색해도, set을 활용하여 지속적으로 중복을 제거해도 99%이후 시간초과가 뜨네요 ㅠㅠ

소스에 근본적인 문제가 있어보입니당...근데 모르겠어요

def calc(l):
    global ans
    ans+=1
    nl=[]
    for a in l:
        nl.append(a-1)
        if a%3==0 and a>=3:
            nl.append(a/3)
        if a%2==0 and a>=2:
            nl.append(a/2)
    return nl

n=int(input())
l=[]
l.append(n)
ans=0
while(1):
    l=calc(l)
    if min(l)==1:
        break
print(ans)

circlezer0 3년 전 2

input 1인 경우

l의 최소값이 0이 됩니다

thdehdx 3년 전 2

안녕하세요 답변 감사드립니다.

위 풀이가 저의 DP 첫 문제였던지라

여러문제 풀다보니 해당 풀이 스타일이 DP답지 못하다(?)라고 느껴지네요

위 답변듣고 input 1인 경우 무한루프도는 것을 발견하여 아래와 같이 "1일 경우 출력하고 끝내는 소스" 추가하여 정답처리 되었습니다.

답변 감사합니다.

def calc(l):
    global ans
    ans+=1
    nl=[]
    for a in l:
        nl.append(a-1)
        if a%3==0 and a>=3:
            nl.append(a/3)
        if a%2==0 and a>=2:
            nl.append(a/2)
    return nl

n=int(input())
l=[]
l.append(n)
ans=0
if n==1:
    print(ans)
else:
    while(1):
        l=calc(l)
        if min(l)==1:
            break
    print(ans)

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

문제

문제

출처

ICPC

[파이썬] 99%성공 후 시간초과

thdehdx 3년 전 0

circlezer0 3년 전 2

thdehdx 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말