글 읽기 - [Python] 다음과 같이 탐욕법으로 접근했을 때 반례가 궁금합니다.

hyh_1016 3년 전 0

다음과 같이 현재의 값에 대해 누적값이 음수일 때는 누적값을 현재값으로 갱신하고 아니면 누적값에 그냥 더한 뒤 max값을 갱신하는 방식으로 탐욕법으로 문제에 접근했습니다.

문제와 게시판의 질문란에 주어진 반례들을 다 통과해서 제출했는데 틀렸습니다가 나와서 다시 DP로 접근해서 풀긴 풀었는데, 이렇게 탐욕법으로 접근했을 때 어디서 논리에 구멍이 생긴건지 궁금해서 질문 남깁니다. 살펴봐주시면 감사하겠습니다!

import sys
input = sys.stdin.readline

n = int(input())
numbers = list(map(int, input().split()))

max_sum = -1001
current_sum = 0
for i in numbers:
    if i > 0 and current_sum < 0:
        current_sum = i
    else:
        current_sum += i
    max_sum = max(max_sum, current_sum)
print(max_sum)

palilo 3년 전 1

-2 -1

hyh_1016 3년 전 0

음수 내림차순이 문제였군요 😂 감사합니다!

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

문제

문제

출처

ICPC

[Python] 다음과 같이 탐욕법으로 접근했을 때 반례가 궁금합니다.

hyh_1016 3년 전 0

palilo 3년 전 1

hyh_1016 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말