사용자 도구

사이트 도구


ps:problems:boj:10274

Equator

ps
링크acmicpc.net/…
출처BOJ
문제 번호10274
문제명Equator
레벨골드 5
분류

dp

시간복잡도O(n)
인풋사이즈n<=1,000,000
사용한 언어Python 3.11
제출기록150212KB / 968ms
최고기록804ms
해결날짜2023/07/27

풀이

  • 최대 부분합 (Maximum subarray problem)을 구하는 문제. 다만 주어진 배열이 원형으로 되어있기 때문에, 부분구간이 두개로 나뉘어져 왼쪽끝과 오른쪽끝에 붙어있는 경우도 고려해야 한다.
  • 원형 배열에서 부분구간을 찾을때 흔히 쓰는 테크닉은 배열을 두번 이어붙인 다음에 찾는 것이지만, 여기에는 바로 적용할수는 없고, 굳이 쓰려면 좀더 로직을 추가해야 하는데 그것보다 더 간단한 방법이 있다.
  • 최대 부분합과 최소 부분합을 모두 찾은 다음에, 최대부분합과 전체합-최소부분합 중에서 큰 값을 택하는 것이다. 최대부분합은 구간이 하나로 되어있을때의 최댓값, 전체합-최소부분합은 구간이 두개로 나눠져있을때의 최댓값에 대응된다.
  • 시간복잡도는 O(n)

코드

"""Solution code for "BOJ 10274. Equator".

- Problem link: https://www.acmicpc.net/problem/10274
- Solution link: http://www.teferi.net/ps/problems/boj/10274

Tags: [dp]
"""

INF = float('inf')


def maximum_subarray(nums):
    max_sum, cur_max_sum = -INF, 0
    min_sum, cur_min_sum = INF, 0
    for num in nums:
        cur_max_sum = max(num, cur_max_sum + num)
        max_sum = max(max_sum, cur_max_sum)
        cur_min_sum = min(num, cur_min_sum + num)
        min_sum = min(min_sum, cur_min_sum)

    return max(0, max_sum), min(0, min_sum)


def main():
    T = int(input())
    for _ in range(T):
        _, *c = [int(x) for x in input().split()]
        max_sum, min_sum = maximum_subarray(c)
        print(max(max_sum, sum(c) - min_sum))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
M J O O F
 
ps/problems/boj/10274.txt · 마지막으로 수정됨: 2023/07/27 14:17 저자 teferi