[BOJ/21758] 꿀 따기 - 풀이 및 코드

21758번: 꿀 따기

문제

풀이

 문제를 단순히 생각하면, 벌통의 위치와 두 꿀벌의 위치를 완전탐색하는 방법이 있지만, 3중 반복문을 사용해야 하기 때문에 시간 초과가 발생하게 됩니다. 또한, 벌통의 위치와 두 꿀벌의 위치가 정해진다고 하더라도 꿀벌의 위치부터 벌통의 위치까지 순회(시뮬레이션)하는 경우, 그에 대한 시간복잡도는 O(N)이기 때문에 최종적으로 O(N^4)의 시간복잡도를 가지게 됩니다.

 

 시간복잡도를 줄이기 위해 문제의 특징을 살펴보겠습니다. 우선, 각 배열에 적혀있는 꿀의 양이 양수이며 꿀벌들은 벌통을 향해서 날라가고 벌통 이후의 꿀들은 채집하지 않습니다. 이러한 조건이 존재하기에 문제의 상황을 다음과 같이 나눠볼 수 있습니다.

 

 벌통을 기준으로 생각하였을 때, 벌통이 양 끝에 존재하는 경우를 생각해봅시다. 앞으로 나오는 케이스는 "벌통의 위치는 여기고, 꿀벌의 위치는 여기다. 따라서 이것이 최대값일 것이다!" 가 아닌, "벌통이 여기 있으면, 꿀벌이 여기 있는게 최선일 것이다!" 라는데 초점을 두고 참조해주시길 바랍니다.

벌통이 맨 끝에 존재하는 경우, 꿀벌 중 한마리(꿀벌1)는 반드시 반대편 끝에 존재해야 함이 자명합니다. 왜냐하면, 꿀벌1이 반대편 끝보다 오른쪽(혹은 왼쪽)에 존재하게 되면 꿀벌이 수집할 수 있는 꿀의 양이 감소하기 때문입니다. (꿀들은 모두 양수이기 때문)

 그렇다면, 꿀벌2는 어디에 존재해야할까요? 

 B2가 만약 B1의 바로 오른편에 존재한다고 가정해봅시다. 그런데, B2의 위치에 존재하는 꿀의 양이 전체 구간의 합 중 대부분을 차지한다면...? 예를 들어, B2의 위치에 1000의 꿀이 존재하고 다른 위치에는 1의 꿀이 존재하며 전체 길이가 10이라고 해봅시다. B2가 B1의 바로 오른편에 존재하게 되면 최댓값을 구하지 못하겠죠. 따라서, B2의 위치는 완전탐색으로 구해줘야 합니다. (시간 복잡도 - O(N))

 

 이번엔, 벌통이 맨 끝에 존재하지 않을 때의 케이스를 확인해보겠습니다.

 위와 같은 경우엔 꿀벌을 어디에 놔야 할까요? 이 때는 양쪽에 꿀벌을 두는 것이 최선입니다.

우선, 꿀벌을 벌통을 기준으로 (왼쪽, 오른쪽)분리시키는 이유부터 설명하자면, 다음과 같은 이유 때문입니다.

 만약, 한쪽에 몰아넣는다면 위 그림과 같이 벌통을 기준으로 왼쪽의 꿀만 수집하게 됩니다. 벌통의 왼편에 존재하는 꿀이 엄청 많다고 가정해도, 꿀의 값은 무조건 양수이기 때문에 이때는 벌통을 가장 오른쪽에 배치하는 것이 가장 많은 꿀을 얻을 수 있으며 그 케이스는 위에서 이미 다뤘습니다. 따라서, 벌통이 맨 끝에 존재하지 않을 때 꿀벌을 벌통을 기준으로 양 옆으로 분리시켜야 올바른 접근입니다.

 양 옆으로 꿀벌을 분리시켰다면, 꿀벌은 당연히 양 끝에 존재하는 것이 최선입니다. 물론 꿀벌이 존재하는 위치가 굉장히 큰 값을 가질 수 있겠지만, 벌통이 가운데로 고정된 이상 최선의 선택은 그것 외에는 없습니다.

 

 벌통의 위치에 따른 최선의 꿀벌의 위치를 구했다면, 벌통을 총 N개의 자리에 위치시키며 각 케이스 별로 획득할 수 있는 꿀의 양을 O(1) 시간 내로 구해주면 됩니다. 이는 누적합을 이용하면 O(1)내 얻을 수 있으며 누적합에 대한 설명은 다른 포스팅에서 하겠습니다. (추후 링크 첨부 예정)

코드

BOJ 코드 치팅 행위는 사용 제재 대상입니다.

 

import sys
input = sys.stdin.readline
n = int(input().rstrip())

A = [0] + list(map(int, input().rstrip().split()))
L = [0 for _ in range(n+1)]
R = [0 for _ in range(n+1)]

# 왼쪽 누적합 선언
for i in range(1, n+1):
    L[i] = L[i-1] + A[i]

# 오른쪽 누적합 선언
R[-1] = A[-1]
for i in range(n-1, 0, -1):
    R[i] = R[i+1] + A[i]

ans = 0

# t의 위치를 처음부터 끝까지 조정하며 최대값을 탐색합니다.
# 단, t가 양 끝에 존재할 땐 꿀벌1은 그 반대편에 존재하며, 꿀벌2의 후보지를 O(n) 시간 내 탐색합니다.
# t가 만약 양 끝에 존재하지 않으면 양 끝에 꿀벌1,2 를 배치하고 답을 갱신합니다
for t in range(1, n+1):
    if 1 < t < n:
        # t가 가운데에 존재한다면 양 끝에서부터의 누적합을 구합니다
        candidate = (L[t] - A[1]) + (R[t] - A[-1])
        ans = max(ans, candidate)
    elif t == 1:
        # t가 맨 왼쪽에 있다면 꿀벌1은 맨 오른쪽에 위치하고, 꿀벌2의 후보지를 탐색합니다
        # 맨 왼쪽부터 맨 오른쪽까지의 합 - 맨 오른쪽 원소
        sum1 = L[-1] - A[-1]
        for i in range(2, n):
            # 맨 왼쪽부터 맨 오른쪽까지의 합 - 맨 오른쪽 원소 + i-1이전의 합 - i 원소의 값
            candidate = sum1 + L[i-1] - A[i]
            ans = max(ans, candidate)
    else:
        # t가 맨 오른쪽에 있다면 꿀벌1은 맨 왼쪽에 위치하고, 꿀벌2의 후보지를 탐색합니다
        # 맨 왼쪽부터 맨 오른쪽까지의 합 - 맨 왼쪽 원소
        sum1 = L[-1] - A[1]
        for i in range(2, n):
            candidate = sum1 + R[i+1] - A[i]
            ans = max(ans, candidate)

print(ans)

참고자료

누적합 추후 추가 예정