글 읽기 - [python] 반례 좀 부탁드립니다.

grapecw 4년 전 0

문제가 분할 정복 문제 인거 같아서 문제를 분할 정복으로 풀었습니다.

그런데 생각나는 반례를 넣어봤는데도 모두 제대로된 값이 반환이 되더군요....

그런데 4% 에서 에러가 뜨는걸 보면 진짜 간단한 반례가 있는거 같던데 반례가 뭔지 찾아 주실 수 있나요?

#https://www.acmicpc.net/problem/1912
import sys

input = sys.stdin.readline

def sumstr(str,start,end) :
    if(start == end) :
        return str[start]
    mid = int((start + end)/2)
    leftsum = sumstr(str, start, mid)
    rightsum = sumstr(str, mid+1, end)

    left = mid
    right = mid + 1
    midsum = 0
    maxmum = -float('INF')

    while True :
        if left < start or right > end :
            break;
        if str[left] > str[right] :
            midsum = midsum + str[left]
            maxmum = max(midsum,maxmum)
            left = left - 1
            if left < start :
                while right <= end :
                    midsum = midsum + str[right]
                    maxmum = max(midsum, maxmum)
                    right = right + 1
        else :
            midsum = midsum + str[right]
            maxmum = max(midsum, maxmum)
            right = right + 1
            if right > end :
                while left >= start :
                    midsum = midsum + str[left]
                    maxmum = max(midsum, maxmum)
                    left = left - 1

    return max(leftsum, rightsum, maxmum)

if __name__ =="__main__":
    n = int(input().strip())

    str = list(map(int,input().strip().split()))

    print(sumstr(str,0,len(str)-1))

djm03178 4년 전 1

틀렸습니다는 답이 틀린 것이지 에러가 아닙니다. 에러라고 말씀하시면 모두 컴파일 에러 또는 런타임 에러를 연상하게 됩니다.

그리고 데이터는 대체로 입력량이 많은 순이기 때문에 일찍 틀렸으면 보통은 매우 큰 데이터에서 틀린 것입니다. 오히려 마지막에 틀려야 매우 간단한 반례가 있는 것입니다.

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

문제

문제

출처

ICPC

[python] 반례 좀 부탁드립니다.

grapecw 4년 전 0

djm03178 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말