[백준 13398] 연속합 2 (Python)

www.acmicpc.net/problem/13398

13398번: 연속합 2

 

문제풀이

N, arr : 입력값

dp : 연속합을 구하기 위한 누적합

- dp[0][i] : 특정 원소를 제거하지 않은 경우
- dp[1][i] : 특정 원소를 제거한 경우

 

dp를 이용한 누적 합 문제이다. N 제한이 100,000 이기에 O(N^2) 이 아닌 그보다 빠른 방식으로 해결해야 한다.

 

1. dp[0][0] 을 arr[0]으로 초기화 한다.

- 최소 1개의 원소는 반드시 선택해야 하기 때문에 dp[0][0] = arr[0] 이다.

 

2. N이 1보다 클 경우 1번 인덱스 원소부터 dp를 진행한다.

- 특정 원소를 제거하는 경우와 제거하지 않는 경우로 나누어서 계산해야 한다.

- dp[0][i] = max(dp[0][i - 1] + arr[i], arr[i]) :  아무런 원소를 제거하지 않았을 때, (이전까지의 연속합 + i번쨰 원소) 와 (i번째 원소)를 비교하여 큰 경우를 대입 => 누적합이 음수가 나올 수 있기 때문

- dp[1][i] = max(dp[0][i - 1], dp[1][i-1] + arr[i]) : 특정 원소를 제거하는 경우는 두 가지를 고려해야 한다 =>

      1. i번째 원소를 제거하는 경우

      2. i번째 이전에서 이미 특정 원소를 제거하여 i번째 원소를 선택하는 경우
   # 1의 경우 dp[0][i - 1](i번째 원소를 제거하였기 때문에 arr[i]를 더해주지 않음)

   # 2의 경우 dp[1][i-1] + arr[i] (이전에 특정 원소를 이미 제거했기 때문에 arr[i]를 더해줌)

 

- N이 1일 경우는 바로 dp[0][0]을 출력한다.

 

3. dp 중 가장 큰 값을 출력한다.

 

코드

import sys

if __name__ == '__main__':
    N = int(input())
    arr = list(map(int, sys.stdin.readline().split()))
    dp = [[0] * N for _ in range(2)]
    # dp[0][i] : 특정 원소를 제거하지 않은 경우
    # dp[1][i] : 특정 원소를 제거한 경우

    dp[0][0] = arr[0] # 1개는 반드시 선택해야 한다.

    if N > 1:
        ans = -1e9
        for i in range(1, N):
            # 아무런 원소를 제거하지 않았을 때, (이전까지의 연속합 + i번쨰 원소) 와 (i번째 원소)를 비교하여 큰 경우를 대입
            dp[0][i] = max(dp[0][i - 1] + arr[i], arr[i])
            # 특정 원소를 제거하는 경우 => 1. i번째 원소를 제거하는 경우 2. i번째 이전에서 이미 특정 원소를 제거하여 i번째 원소를 선택하는 경우
            # 1의 경우 dp[0][i - 1] 2의 경우 dp[1][i-1] + arr[i]
            dp[1][i] = max(dp[0][i - 1], dp[1][i-1] + arr[i])
            # dp 진행 중 가장 큰 값으로 갱신
            ans = max(ans, dp[0][i], dp[1][i])
        print(ans)
    else: # N이 1인 경우는 반드시 선택을 해야하므로 dp[0][0] 출력
        print(dp[0][0])

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!