BOJ_13398 [ 연속합 2 ] [ 파이썬 ]

문제

https://www.acmicpc.net/problem/13398

13398번: 연속합 2

문제 해결 방법

다이나믹 프로그래밍으로 문제를 해결해야 된다.

숫자를 하나 제거할 수 있기 때문에 제거 한경우와 안한경우로 나누어서 최대값을 갱신해야된다.

DP [제거플래그][ 숫자인덱스]  제거 플래그가 0이면 한번도 제거를 안한 경우이고 1이면 한번 제거를 한 경우이다.

DP[0][i] = max( 이전 제거안한 dp값에 + 현재 숫자, 현재 숫자)

DP[1][i] = max( 이전 제거안한 숫자 , 이전 제거한 숫자 + 현재 숫자) // 현재 숫자를 제거한 경우 또는 이전에 숫자를 제거한 경우

소스 코드 보기

https://github.com/jokerKwu/BOJ_Algorithm/blob/master/python/BOJ_13398.py

jokerKwu/BOJ_Algorithm

import sys
input = sys.stdin.readline
N = int(input())
arr = []
arr = list(map(int, input().split()))
dp = [ [0]*(N+2) for _ in range(2) ]
dp[0][0] = arr[0]       # 0이 제거를 안하는거
dp[1][0] = 0            # 1이 제거를 하는거
answer = arr[0]
for i in range(1, N):
    dp[0][i] = max(dp[0][i-1]+arr[i], arr[i])           # 기존 숫자 이어서 하던지, 현재 숫자만
    dp[1][i] = max(dp[0][i-1], dp[1][i-1]+arr[i])       # 현재 숫자를 제거, 기존 숫자제거 + 현재 숫자
    answer = max({dp[0][i],dp[1][i],answer})
print(answer)