[BOJ] 보석 구매하기 - 2313 (G5)

시간 제한	메모리 제한
2 초	128 MB

문제

N개의 보석 가게에서 보석을 하나씩 사려고 한다. 각 보석 가게에는 연속된 선반에 여러 개의 보석이 진열되어 있다. 상진이는 각 가게에서 연속된 구간의 보석들을 구매하되, 그 구간의 보석 가치의 합을 최대로 하고 싶다.

풀이

최대 부분 배열(Maximum Subarray) 문제와 누적 합을 이용한 문제이다.

코드

INF = float('inf')

n = int(input())

total_sum = 0
select_idx = []
for _ in range(n):
    L = int(input())
    jewels = list(map(int, input().split()))

    cum_sum = [0] * (L + 1)
    for i in range(1, L + 1):
        cum_sum[i] += cum_sum[i - 1] + jewels[i - 1]
    
    max_sum = -INF
    max_start = 1
    max_end = L

    for k in range(L, 0, -1):
        is_max = False
        for i in range(0, L - k + 1):
            part_sum = cum_sum[k + i] - cum_sum[i]
            if max_sum > part_sum:
                continue
            # 최대값과 같고 이미 앞에서 그 값이 나온 경우
            elif max_sum == part_sum and is_max:
                continue

            max_sum = part_sum
            max_start = i + 1
            max_end = k + i
            is_max = True
    total_sum += max_sum
    select_idx.append((max_start, max_end))


print(total_sum)
for result in select_idx:
    print(*result)

시간 복잡도

O(N × L^2)