동적 프로그래밍 : 연속합(백준 1912번)

▶ 문제 : https://www.acmicpc.net/problem/1912

1912번: 연속합

##### 문제 #####
# n개의 정수로 이루어진 임의의 수열이 주어진다. 
# 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 
# 가장 큰 합을 구하려고 한다. 
# 단, 수는 한 개 이상 선택해야 한다.

##### 입력 #####
# 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 
# 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 
# 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

##### 출력 #####
# 첫째 줄에 답을 출력한다.

 

▶ 접근 방법

동적 프로그래밍을 이해하는데 도움이 되는 기본적인 문제였다.

우선, 숫자들이 담겨 있는 numbers라는 리스트를  입력받는다.
numbers = [10, -4, 3, 1, 5, 6, -35, 12, 21, -1]

문제의 요구 사항은 해당 리스트에서 연속된 숫자들을 선택하여 최대의 값을 만드는 것이었다.
해당 요구 사항을 반영하여 DP 테이블을 만든다고 했을 때,
DP[1]는 numbers[1]로 끝나는 연속된 숫자의 최대값을 의미한다.
즉, DP[1]는 10과 -4의 합인 6이다.

이런 방식으로 numbers[n-1]로 끝나는 연속된 숫자의 최대값까지 모두 구해서 
DP 테이블을 완성하고, 해당 테이블의 최대값을 구하면 
그 값이 numbers 리스트에서 연속된 숫자들을 선택하여 만든 최대값이다.

 

▶ 풀이 코드

import sys

N = int(sys.stdin.readline().rstrip())
numbers = list(map(int, sys.stdin.readline().split()))

DP = [0] * N 
DP[0] = numbers[0]

for i in range(1, N):
    DP[i] = max(DP[i-1]+numbers[i], numbers[i])

print(max(DP))

 

▶ 관련 링크

 

2021.11.25 - [알고리즘] - 동적 프로그래밍(Dynamic Programming)이란?

2021.11.25 - [알고리즘] - 동적 프로그래밍 : 피보나치 수 2(백준 2748번)

2021.11.25 - [알고리즘] - 동적 프로그래밍 : 01타일(백준 1904번)

2021.11.26 - [알고리즘] - 동적 프로그래밍 : 평범한 배낭(백준 12865번)

2021.11.27 - [알고리즘] - 동적 프로그래밍 : 동전(백준 9084번)

2021.11.27 - [알고리즘] - 동적 프로그래밍 : LCS(백준 9251번)

2021.11.27 - [알고리즘] - 동적 프로그래밍 : 가장 긴 증가하는 부분 수열(백준 11053번)

2021.11.29 - [알고리즘] - 동적 프로그래밍 : 점프(백준 2253번)