글 읽기 - 이 문제 그냥 포기해야하나요?

dhrmsry7 4년 전 0

https://www.acmicpc.net/blog/view/12

여기에 설명 그대로 재귀를 이용하여 코드를 짜봐도

25퍼센트에서 런타임에러가 납니다

런타임에러가 나는 이유까지 다 찾아서 확인해봤지만

알수가없습니다..

전에 질문을올렸는데 답변 받지못했고

이 질문까지 답변을 받지못하면 그냥 포기할 생각입니다 ㅋㅋ..

이유를 알려주실 고수분 안계신가요

import sys
import math


def init(a, tree, node, start, end):#배열 a, 세그먼트 트리, 노드번호
    if start==end:#리프노드일때(함수가 계속호출되어 start=end가 되고, 그만큼 node도 2배씩 커져서 끝까지 내려가게됨)
        tree[node]=start
    else:
        init(a, tree, node*2, start,int((start+end)/2))
        init(a, tree, node*2+1, int((start+end)/2+1), end)
        tree[node]= (lambda x ,y: x if a[x]<a[y] else y) (tree[node*2],tree[node*2+1])
        

#구간에서 제일 작은 값을 찾음(h의)
def query(a, tree, node, start, end, left, right):
    if left>end or right<start: #겹치지 않을때
        return -1
    if left<=start and end<=right:#start~end가 left~right포함
        return tree[node] #트리의 값 반환: a의 구간에서의 최소값 반환

    m1 = query(a,tree,2*node,start, int((start+end)/2), left, right)
    m2 = query(a,tree,2*node+1,int((start+end)/2)+1,end,left,right)
    if m1==-1:
        return m2
    elif m2==-1:
        return m1
    else:
        if a[m1] <=a[m2]:
            return m1
        else:
            return m2

#제일큰 직사각형넓이 갱신
def largest(a, tree, start, end):
    n = len(a)
    m = query(a,tree, 1, 0, n-1, start, end)
    area = a[m]*(end-start+1)

    if start <= m-1:
        temp=largest(a,tree,start,m-1)
        if temp>area:
            area=temp
    if end>=m+1:
        temp=largest(a,tree,m+1,end)
        if temp>area:
            area=temp
    return area

while True:
    temp=list(map(int,input().split()))
    n=temp[0]
    h=temp[1:]
    if n==0:
        exit(0)
    tree=[0]*(2**(math.ceil(math.log(n,2))+1))#트리인덱스 1부터시작
    init(h,tree,1,0,n-1)
    print(largest(h,tree,0,n-1))

evenharder 4년 전 0

우선, exit(0)를 Python에서 그대로 사용하면 런타임 에러가 납니다. sys.exit(0)을 사용하셔야 합니다.

그리고 Python은 재귀 깊이가 기본적으로 적은 값으로 설정되어 있어 재귀함수가 깊게 들어갈 수 없는 경우가 많습니다.

이를 해결하는 방법이 sys.setrecursionlimit 함수입니다.

sys.setrecursionlimit(101000) 으로 설정하고 sys.exit(0)으로 바꾸니 50%에서 런타임 에러가 발생하네요.

그리고 Python보다는 PyPy쪽에 제출하는 게 시간측면에서 나을 수 있습니다.

evenharder 4년 전 0

약간 잘못 썼네요. 다시 확인해본 결과 exit(0)는 PyPy에서만 에러가 납니다. 하지만 재귀 깊이 때문에 런타임 에러가 25%에서 난 것 같긴 합니다.

evenharder 4년 전 2

로컬에서

n=10000
h=[1000*(i+1) for i in range(n)]

로 놓고 해보았는데 프로그램이 비정상적으로 종료되었습니다. RecursionError가 아닌 MemoryError였습니다.

제 생각엔 largest 함수에서 직접적인 재귀를 사용하는 것보다, while문을 돌면서 start / end를 바꾸며 답을 갱신하는 식으로 하면 될 것 같습니다.

예를 들어, largest 내부에서 largest를 호출하기보다 start/end값을 바꾸고, 다시 query를 부르고...하는 식입니다.

Python의 재귀가 C/C++보다는 오버헤드가 많이 큰 것 같습니다.

dhrmsry7 4년 전 0

답변해주셔서 정말감사합니다!ㅎㅎ

재귀를 반복문으로 바꾸는게 쉽지않겠지만 해보겠습니다!

dhrmsry7 4년 전 0

재귀를 반복문으로 바뀌는게 감이안잡히네요..

이렇게 바꾸니 시간초과가 나고..

def largest(a, tree, start, end):
    n=len(a)
    result=a
    while start<end:
        m = query(a,tree, 1, 0, n-1, start, end)#최소높이
        result.append(a[m]*(end-start+1))#사각형 크기 저장
        
        while start<end:
            if m-1>start:
                end=m-1#앞에 부분
                m = query(a,tree, 1, 0, n-1, start, end)#앞의부분의 최소높이
                result.append(a[m]*(end-start+1))#사각형크기 저장
            else: break
                
        if m+1<end:
            end=n-1
            start=m+1#뒤에부분
            m = query(a,tree,1,0,n-1,start,end)
            result.append(a[m]*(end-start+1))
        else: break
    return max(result)

dhrmsry7 4년 전 1

while문 안에 스택을 이용해서 해결했습니다!

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

문제

문제

출처

ICPC

이 문제 그냥 포기해야하나요?

dhrmsry7 4년 전 0

evenharder 4년 전 0

evenharder 4년 전 0

evenharder 4년 전 2

dhrmsry7 4년 전 0

dhrmsry7 4년 전 0

dhrmsry7 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말