글 읽기 - 파이썬 25프로 반례를 도저히 모르겠습니다.

q6801 3년 전 0

문제를 분할 정복을 이용해서 풀어보았는데 25프로에서 틀렸습니다가 나옵니다. 코드의 어떤 부분이 잘못되었는지 굉장히 고치고 싶습니다. 반례를 부탁드립니다.

import sys


def divideConquer(left, right, li):
    mid = (left + right) // 2
    if left == right:
        return li[left]
    mid0 = mid
    mid1 = mid + 1

    min_height = li[mid0]
    max_width = 0
    max_area = 0

    check0 = False
    check1 = False
    while True:
        if check0 and check1:
            break

        if not check0 and mid0 >= left:
            temp_area = min([min_height, li[mid0]]) * (max_width + 1)
            if max_area <= temp_area:
                min_height = min([min_height, li[mid0]])
                mid0 -= 1
                max_width += 1
                max_area = temp_area
            else:
                check0 = True
        else:
            check0 = True

        if not check1 and mid1 <= right:
            temp_area = min([min_height, li[mid1]]) * (max_width + 1)
            if max_area <= temp_area:
                min_height = min([min_height, li[mid1]])
                mid1 += 1
                max_width += 1
                max_area = temp_area
            else:
                check1 = True
        else:
            check1 = True

    return max([divideConquer(left, mid, li), divideConquer(mid+1, right, li), max_area])

if __name__ == "__main__":
    sys.setrecursionlimit(101000)
    li = []
    while True:
        li2 = list(map(int, sys.stdin.readline().split()))
        if li2[0] == 0:
            break
        li2.pop(0)
        li.append(li2)

    for l in li:
        print(divideConquer(0, len(l)-1, l))

rail 3년 전 2

입력 : 5 1 2 3 4 5

정답은 9인데 해당 프로그램은 8을 출력하네요.

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

문제

문제

출처

ICPC

파이썬 25프로 반례를 도저히 모르겠습니다.

q6801 3년 전 0

rail 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말