[백준/BOJ/C언어] 10211번 :: Maximum Subarray

문제 링크

 

 

 

Solution

---

반복문을 이용해서 부분 배열의 합을 구하려고 하면 시작점과 끝점을 바꿔 가면서 값을 구해야 하기 때문에 반복문을 최소 두 번은 중첩해서 사용하게 된다. 그러면 시간 초과가 나기 때문에, 반복문을 중첩하는 방법으로는 AC를 받을 수 없다. 그런데 DP를 이용하면 선형 시간 안에 이 문제를 해결할 수 있다. 부분 배열의 합을 저장하는 배열을 하나 더 만든다고 생각해 보자. 이 배열의 이름을 dp라고 하면, dp[i]는 해당 인덱스까지의 부분 배열의 합을 의미한다.

 

주어진 배열이 -1 -2 -5 6 1이라고 가정하자. 편의상 인덱스가 1부터 시작한다고 생각하고 dp의 값을 구하면 dp[1]은 -1이 될 것이다. dp[2]는 dp[1]에 -2를 더한 값이 되는데, 이는 dp[1]보다 작다. 따라서 최대값이 될 수 없다. 그러면 dp[2]에는 무슨 숫자를 넣어 줘야 할까? 우리는 뒤에 아직 어떤 숫자가 올지 모르고, 어디서부터 시작해야 최대 부분 배열의 합이 되는지 모른다. 어쩌면 -2가 부분 배열의 합이 될지도 모른다. 하지만 당장 dp[2]는 최대값이 될 수 없음을 알고 있다. 그래서 다음 타자가 사용할 수 있게, dp[2]는 -2, 즉 숫자 배열의 같은 인덱스의 요솟값을 그대로 할당해 준다. (실제 코드에서는 이 할당을 먼저 한다. 왜? 계산 결과가 어떨지 모르니까.)

 

다음으로 넘어가서 dp[3]도 같은 이유로 -5가 된다. 이제 dp[4]에 이르렀다. 일단 숫자 배열의 같은 인덱스의 요솟값인 6을 할당한다. dp[3]에 5를 더한 것보다 dp[4], 현재 숫자 배열의 4번째 값이 크다. dp[4]는 그대로 둔다. 최댓값이 업데이트된다. 마지막으로 dp[5]에 일단 1을 할당한다. 1에 dp[4]를 더한 값이 dp[5]보다 크다. dp 배열이 제 할 일을 할 때가 왔다. dp[5] 값을 1+dp[4]로 업데이트한다. 이 값이 dp[4]보다 크므로 최대값이 업데이트되고, 최종적으로 이 값이 답이 된다.

 

 

code

---

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
#include <string.h>
using namespace std;

int dp[1001];
int arr[1001];

int main() {
    int TC, N,  maxSum;
    scanf("%d", &TC);
    while (TC--) {
        memset(dp, 0, sizeof(dp));
        maxSum = INT_MIN;
        scanf("%d", &N);
        for (int i = 1; i <= N; i++) {
            scanf("%d", &arr[i]);
        }


        for (int i = 1; i <= N; i++) {
            dp[i] = arr[i];
            if (arr[i] + dp[i - 1] > dp[i]) {
                dp[i] = arr[i] + dp[i - 1];
            }
            maxSum = max(maxSum, dp[i]);
        }

        printf("%d\n", maxSum);

    }

    return 0;
}