[BOJ] 1912 연속합 - 동적계획법 풀이

* 동적계획법이란?
https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95

동적 계획법 - 위키백과, 우리 모두의 백과사전

동적 계획법 수학과 컴퓨터 공학, 그리고 경제학에서 동적 계획법 (動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. 설명 [ 편집 ] 동적 계획법의 원리는 매우 간단하다. 일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위

ko.wikipedia.org

* 문제
n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 숫자는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

* 풀이
수열의 원소중 연속된 숫자를 선택해 가장 큰 합을 구하기 위해서 동적계획법(Dynamic Programming)을 사용합니다. 첫번째 원소부터 별도의 배열(dp배열)에 수열값과 그전까지 합한 값 중 큰값을 저장합니다. 그중 최댓값을 구하면 정답입니다. 이해가 안가시면 아래 코드를 주석과 함께 한 줄 씩 해석해 보시기 바랍니다.

* 소스코드

#include <iostream> 
#define MAX(a,b) ((a) > (b) ? (a) : (b)) 
using namespace std; 

int main(){ 
     int input_value = 0; 
     cin >> input_value; 
     int *data = new int[input_value]; 
     int *dp = new int[input_value];  // 배열 동적 할당
     int max = -1001; // max는 입력 값 중 가장 작은값보다 작은값

     for (int i = 0; i < input_value; i++)  
          cin >> data[i]; // 데이터 입력

     dp[0] = data[0]; // 첫번째 원소는 그대로 대입(그 자체로 최대값)

     for (int i = 1; i < input_value; i++) 
          dp[i] = MAX(data[i], data[i] + dp[i - 1]); 
          // dp배열에 원소 값과 그전 dp값을 합한 값 중 큰 값 대입

     for (int i = 0; i < input_value; i++) 
          if (max < dp[i]) max = dp[i]; // 최댓값 검색

     cout << max; 

     delete[] dp; 
     delete[] data; // 배열 동적 할당 메모리 해제

     return 0; 
}

질문 및 오류사항은 댓글로 달아주세요.