백준 1912- 연속합(다이나믹 프로그래밍)

문제

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

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

 

입력

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

출력

첫째 줄에 답을 출력한다.

 

---------------------------------------------------------------------------------------------------------------

 

 

 

1. 첫번째 시도.

누적합을 통해서 다이나믹 프로그래밍을 어느정도 구현할 수 있다고 생각했다.

그리고 i부터 j(i <= j)까지의 연속합은 j까지의 누적합 - (i-1)까지의 누적합. 이라고 구현하고 풀려고 했다. (i=0일 때는 j까지의 누적합)

 

구현법은 

sum 배열에 0인덱스부터 차례로 누적합을 저장하는 방법이다.

#include <stdio.h>

int num[100001];
int N;
int sum[100001];

int main()
{
    int max=-1987654;
    int ret;
    scanf("%d", &N);
    for(int i=0;i<N;i++)
        scanf("%d", &num[i]);
    sum[0] =num[0];
    for(int i=1;i<N;i++)
        sum[i]= sum[i-1] + num[i];
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(j !=0)
                ret = sum[i] - sum[j-1];
            else
                ret = sum[i];
            //printf("%d ", ret);
            if(ret > max)
                max = ret;
        }
        //printf("\n");

    }
    printf("%d", max);

}

이 방법은 시간초과로 인해 실패했다.

아무래도 최대 연속합을 구하는데 누적합을 이중 for문으로 도는 것이 성능상 최적은 아닐 거라고 생각했다.

 

 

 

 

2. 두번째 시도.

연속합의 최대는

1. 누적합 배열에서 최댓값

2. 누적합 배열에서 최대값 - 그 보다 작은 인덱스 범위에서 최소값

이기도 하다.

 

단, 최솟값인 인덱스가 최댓값인 인덱스보다 작다는 조건이 있으므로, 마냥 최대 최소를 구한다고 구할 수 있는 건 아니다. 

최대인지 아닌지를 알려면 누적합에서 그 전 범위에서 가장 작은값을 뺀 값이 최대인지 아닌지를 알면된다.

 

예를 들어서

10 -4 3 1 5 6 -35 12 21 -1 입력이 있을 때, 

누적합은

10 6 9 10 15 21 -14 -2 19 18 이고,

누적합 최소는

10 6 6 6 6 6 6 6 -14 -14 -14 -14 라고 저장되어있을 때, 

 

 

마지막 연속 숫자가 0 인덱스인 최대 연속합은 

max(10 - 0 = 10, 10-10 = 0)  =10

1인덱스까지 최대 연속합은 

max(6-0 = 6, 6-6 =0) = 6

2 인덱스까지 최대 연속합은

max(9-0 = 9, 9-6 = 3) = 9

3 인덱스까지 최대 연속합은

max(10-0 = 10, 10-6 = 4) = 10

4 인덱스까지 최대 연속합은

max(15-0= 15, 15-6 = 9) = 15

5 인덱스까지 최대 연속합은 

max(21-0 = 21, 21-5= 15) = 21

6 인덱스까지 최대 연속합은

max(-14-0 = -14, -14-6 = -20) =  -14

7 인덱스까지 최대 연속합은

max(-2=0 = -2 , -2-(-14) = 12) = 12

8 인덱스까지 최대 연속합은

max(19-0, 19-(-14) = 33) =  33

9 인덱스까지 최대 연속합은

max(18-0 = 18, 18-(-14) = 32) = 32

이다. 

 

이 중 최대는 33이므로, 찾을 수 있다.

 

 

가독성을 높인 그림을 첨부하였다. 

 

 

 

구현은 다음과 같이 하였다. 

#include <stdio.h>

int num[100001];
int N;
int sum[100001];
int min[100001];

int main()
{
    int max=-1987654;
    int ret,minnum;
    scanf("%d", &N);
    for(int i=0;i<N;i++)
    {
        scanf("%d", &num[i]);
    }
    sum[0] =num[0];
    for(int i=1;i<N;i++)
        sum[i]= sum[i-1] + num[i];
    minnum = sum[0];
    for(int i=0;i<N;i++)
    {
        min[i] = minnum;
        if(sum[i] < minnum)
            minnum = sum[i];
    }

    for(int i=0;i<N;i++)
    {
        if(i != 0)
            ret = sum[i]-min[i];
        else
            ret = sum[i];
       if(ret < sum[i])
           ret = sum[i];

       if(ret > max)
           max = ret;
    }
    printf("%d", max);

}