글 읽기 - [Python] 시간초과 질문 드립니다.

parksjin01 7년 전 0

예제 답은 나오는데 계속 시간초과가 발생합니다.

시간을 줄이려고 최대한 반복문도 줄였는데

더이상 어떻게 해야 시간이 줄지 감이 잡히지 않습니다.

도와주세요 고수님들

import sys
sys.setrecursionlimit(200000)
def sticker(stickers, x, y, length, cache):
    if x >= length:
        return 0

    try:
        return cache[(x, y)]
    except:
        pass

    if y == 1:
        m=max(sticker(stickers, x+1, 0,length, cache)+stickers[y][x], sticker(stickers, x+2, y,length, cache)+stickers[y][x], sticker(stickers, x+1, 0,length, cache), sticker(stickers, x+1, y,length, cache))
    else:
        m=max(sticker(stickers, x+1, 1,length, cache)+stickers[y][x], sticker(stickers, x+2, y,length,  cache)+stickers[y][x], sticker(stickers, x+1, 1,length, cache), sticker(stickers, x+1, y,length, cache))
    cache[(x, y)]=m
    return cache[(x, y)]

test=input()
for i in range(test):
    cache={}
    stickers=[]
    lenght=input()
    stickers.append(map(int, raw_input().split(' ')))
    stickers.append(map(int, raw_input().split(' ')))
    print max(sticker(stickers, 0, 0, lenght, cache), sticker(stickers, 0, 1, lenght, cache))

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

문제

문제

출처

ICPC

[Python] 시간초과 질문 드립니다.

parksjin01 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말