글 읽기 - (python 3) 자꾸 시간 초과가 뜨네요.

wldnd1107 5년 전 0

자꾸 16%에서 33%로 넘어가면서 시간 초과가 뜹니다.

인터넷에 있는 테스트 케이스를 넣었는데 값은 잘 나오고,

알고리즘은 블로그에 있는 분할 정복 알고리즘으로 짰습니다.

https://www.acmicpc.net/blog/v...

import sys # sys로 input을 받습니다.

def Maximum_Area(n,arr1):
    global maximum_area
    
    if arr1==[]:
        return
    if n==1:
        maximum_area=max(arr1[0],maximum_area)
        return
    if n==2:
        maximum_area=max(max(arr1),2*min(arr1),maximum_area)
        return # n==0,1,2인 경우는 바로 maximum_area를 갱신하도록 하였습니다.

    minimum=1000000001
    index=[]
    
    for i in range(n):
        if arr1[i]==minimum:
            index.append(i)
        if arr1[i]<minimum:
            minimum=arr1[i]
            index=[i] # minimum을 찾으면서 해당 위치를 index에 저장하였습니다.

    l=len(index)

    maximum_area=max(n*minimum,maximum_area) # 높이가 가장 낮은 직사각형의 넓이와 비교하여 갱신합니다.
    
    if index[0]!=0:
        Maximum_Area(index[0],arr1[0:index[0]])
            
    if index[-1]!=n-1:
        Maximum_Area(n-index[-1]-1,arr1[index[-1]+1:])
        
    for j in range(1,l):
        Maximum_Area(index[j]-index[j-1]-1,arr1[index[j-1]+1:index[j]])
        
    return # minimum의 직사각형을 제외하고 재귀함수를 돌렸습니다.


####################################################

arr=list(map(int, sys.stdin.readline().split()))
n=arr[0] # 입력받고

while n!=0:
    maximum_area=0

    Maximum_Area(n,arr[1:]) # 함수에 값을 넣습니다.

    print(maximum_area) # 출력.

    # print(arr[1:])    
    arr=list(map(int, sys.stdin.readline().split()))
    n=arr[0] #0을 받을 때까지 while문이 돌아갑니다.

indioindio 5년 전 3

100000 0 1 2 3 4 .... 99999

같은 입력에서 시간초과가 나네요.

귀찮으실까봐 입력의 생성기까지 넣어드릴게요.

import random

print(100000, end=' ')
print(*(range(100000)))
print(0)

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

문제

문제

출처

ICPC

(python 3) 자꾸 시간 초과가 뜨네요.

wldnd1107 5년 전 0

indioindio 5년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말