🐹 연속합 2

1. 문제 링크

13398번: 연속합 2

2. 코드

Python3 42828KB 204ms

INF = int(1e9)

n = int(input())
numbers = list(map(int, input().split()))
dp = [[0] * 2 for _ in range(n)]
dp[0][0] = numbers[0]
dp[0][1] = numbers[0]

for i in range(1, n):
    # 숫자를 제외하지 않을 경우
    dp[i][0] = max(dp[i-1][0] + numbers[i], numbers[i])
    # 하나의 숫자를 제외할 경우
    dp[i][1] = max(dp[i-1][0], dp[i-1][1] + numbers[i])

result = -INF
for d in dp:
    result = max(result, max(d))
print(result)

3. 해설

dp 테이블을 연속합에서 하나의 숫자를 제외하지 않은 경우 ‘0’과 제외한 경우 ‘1’을 구분하여 이차원 배열로 초기화한다.

숫자 한 개 이상은 무조건 사용해야 하므로 dp[0]의 시작을 두 케이스 모두 수열의 가장 첫 값으로 초기화한다.

• 숫자가 제외되지 않은 연속합의 최댓값 dp[i][0]

  (이전까지 합해온 숫자 + 현재 본인의 값)과 (현재 본인의 값)을 비교해봤을 때 (현재 본인의 값)이 더 크다면 이전 합을 추가해줄 필요가 없다.

  dp[i-1] + numbers[i] (이전까지 합해온 숫자 + 현재 본인의 값) / numbers[i] (현재 본인의 값)

  → dp[i][0] = max(dp[i-1][0] + numbers[i], numbers[i])

• 숫자가 제외되었을 때 연속합의 최댓값 dp[i][1]

  dp[i][1]은 현재까지 숫자 하나는 무조건 제외된 상태를 의미한다.

  두 가지 경우 중 큰 경우를 고르면 된다.

  1. 현재 수까지는 한 번도 제외하지 않았고, 현재 값을 제외할 경우 → dp[i-1][0]
  2. 이미 앞에서 제외한 경우에 현재 값을 더하는 경우 → dp[i-1][1] + numbers[i]

  → dp[i][1] = max(dp[i-1][0], dp[i-1][1] + numbers[i]