글 읽기 - 살려주세요 시간초과 이유를 도저히 모르겠어 질문드립니다 (python)

dngp93 2년 전 0

어떻게든 혼자 클리어 하려다 마지막 시간초과의 벽을 못넘네요.

정답 코드까지 참고하여 성공한 코드와 로직도 같고

질문 게시판 있는 모든 반례들 다 작동하는데 시간초과가 납니다

1. 함수의 매개변수로 list를 넣은 점

2. arr[:]과 같은 list 슬라이싱(?)을 사용한 점

3. ....

도저히 무엇이 이유인지를 모르겠습니다.

도움 주시면 정말 감사하겠습니다

import sys
input = sys.stdin.readline

def histogram(arr:list) -> int:
    if len(arr) == 1:
        return arr[0]
    else:
        pl = 0
        pr = len(arr) - 1
        pc = (pl+pr)//2
        
        arr_l = arr[:pc + 1]
        arr_r = arr[pc + 1:]
        left_histo = histogram(arr_l)
        right_histo = histogram(arr_r)
        s = min(arr) * len(arr)
        lo = pc
        hi = pc + 1

        while pl < lo or hi < pr:            
            tmp = min(arr[lo:hi+1]) * (hi - lo + 1)
            s = max(s, tmp)            

            count += 1

            if lo == pl:
                hi += 1
                continue
            elif hi == pr:
                lo -= 1
                continue
            else:
                if arr[lo - 1] > arr[hi + 1]:
                    lo -= 1
                else:
                    hi += 1    
            
        return max(left_histo, right_histo, s)


while 1:
    heights = list(map(int, input().split()))
    if len(heights) == 1 and heights[0] == 0:
        break
    n = heights[0]
    heights.pop(0)
    
    print(histogram(heights))

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

문제

문제

출처

ICPC

살려주세요 시간초과 이유를 도저히 모르겠어 질문드립니다 (python)

dngp93 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말