[백준] 4008 특공대 Python 3

데크 - 누적 합, 동적 프로그래밍(DP) 및 데크를 결합하여 큰 데이터 세트를 효율적으로 처리하는 데 유용합니다.

문제 개요

N명의 병사가 주어졌을 때, 각 병사는 특정 전투력 값을 가지고 있습니다. 우리는 A, B, C라는 세 개의 계수를 사용하여 일련의 계산을 통해 전투력을 최대화하고자 합니다. 이 솔루션의 핵심은 데크를 사용하여 선형 함수를 효율적으로 관리함으로써 DP 전환을 최적화하는 것입니다.

함수 T 설명

함수 T(i, j, A, B)는 주어진 계수 A와 B 아래에서 점 i와 j로 정의된 두 직선의 교점을 계산합니다. 이 함수는 선이 더 이상 유효하지 않고 데크에서 제거될 수 있는지를 결정하는 데 중요한 역할을 합니다.

 

전체 코드

다음은 전체 코드입니다:

import sys
from collections import deque

# 두 직선 i와 j의 교점을 계산하는 함수
def T(i, j, A, B):
    c, d = i
    e, f = j
    return (A * (e ** 2 - c ** 2) - B * (e - c) + f - d) / (2 * A * (e - c))

def main():
    # 입력을 읽고 공백을 기준으로 나눔
    input = sys.stdin.read
    data = input().split()
    
    # 첫 번째 값은 N (병사 수)
    N = int(data[0])
    # 그 다음 세 값은 A, B, C (계수)
    A, B, C = map(int, data[1:4])
    # 나머지 값들은 병사의 전투력 값
    values = list(map(int, data[4:]))

    # 누적 합과 DP 배열 초기화
    pre_sum = 0
    dp = 0
    # 초기 deque 설정, 첫 번째 값 (0, 0) 추가
    E = deque([(0, 0)])

    # 병사의 전투력 값을 순회하며 처리
    for t in values:
        pre_sum += t  # 현재 전투력 값을 누적
        
        # deque의 앞에서부터 불필요한 직선 제거
        while len(E) > 1 and T(E[0], E[1], A, B) < pre_sum:
            E.popleft()
        
        # 현재 deque의 첫 번째 직선에서 dp 값 계산
        e, f = E[0]
        dp = -2 * A * e * pre_sum + A * e ** 2 - B * e + f + A * pre_sum ** 2 + B * pre_sum + C
        
        # 새로운 직선이 추가될 때 교점을 기준으로 불필요한 직선 제거
        while len(E) > 1 and T((pre_sum, dp), E[-2], A, B) < T(E[-1], E[-2], A, B):
            E.pop()
        
        # 새로운 직선을 deque에 추가
        E.append((pre_sum, dp))

    # 최종 결과 출력
    print(E[-1][1])

if __name__ == "__main__":
    main()

주요 알고리즘

1. 입력 읽기 및 초기화:
   • 표준 입력에서 입력을 읽습니다.
   • 병사 수 N과 계수 A, B, C를 추출합니다.
   • 병사들의 전투력 값을 values 리스트에 저장합니다.
2. 누적 합 및 DP 초기화:
   • pre_sum은 전투력의 누적 합을 추적합니다.
   • dp는 동적 프로그래밍 결과를 저장합니다.
   • 데크 E는 첫 번째 요소 (0, 0)으로 초기화되어 초기 상태를 나타냅니다.
3. 각 병사의 전투력 처리:
   • 각 전투력 t에 대해 누적 합 pre_sum을 업데이트합니다.
   • 데크를 사용하여 현재 누적 합과의 교차점을 확인하여 더 이상 필요하지 않은 선을 제거합니다.
   • 데크의 현재 상태를 사용하여 새로운 dp 값을 계산합니다.
   • 새로운 상태를 데크에 삽입하고 교차점을 비교하여 유효한 선만 남도록 합니다.
4. 결과 출력:
   • 마지막으로 최대 전투력 값을 출력합니다.