< BOJ > 1912 - 연속합

문제

https://www.acmicpc.net/problem/1912

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 

10 10 -4 3 1 5 6 -35 12 21 -1

예제 출력 1 

33

코드

#include<stdio.h>
#include<stdlib.h>

#define max(a,b) (a)>(b) ? a : b;
int *d;
int n;
int *arr;
int max;


void input(){
    scanf("%d",&n);
    arr = (int *)calloc(n+1,sizeof(int));
    d = (int *)calloc(n+1,sizeof(int));
    int i;
    for(i=1;i<=n;i++){
        scanf("%d",&arr[i]);
    }
    max = arr[1];
}
int solve(int n){

    if(n==1){
        return d[n] = arr[n];
    }
    else if(d[n]!=0){
        return d[n];
    }
    else{
        d[n] = max(solve(n-1)+arr[n],arr[n]);
    }
    if(max<d[n]) max = d[n];
    return d[n];
}

void output(){
    printf("%d\n",max);
}


int main(){
    input();
    solve(n);
    output();
    return 0;
}

 

해결 방법

d[n] 에 저장하는 부분을 앞까지의 전체 배열의 합으로 계산하게 만들었다. 

d[n-1]+arr[n] , arr[n] 중에 큰 것을 선택하게 한 이유는 위의 예제에서 -35처럼 앞의 것을 더했는데 뒤의 새로운 값보다 작다면 앞의것과 함꼐 더하는 것 보다 새로운 것만 더하는 것이 더 큰값을 갖기 때문에 그렇게 설정하도록 만들었다. 

즉 arr[n]이 더 큰 경우에는 새로운 부분부터 더할 수 있도록 만들어주는 것이 목표이다.

ex. -35까지 더한 것에 12를 더하는 것은 -2 지만 새로운 12만을 선택하면 부분합이 제일 큰 경우가 12이므로 그것을 선택해서 새로운 부분합을 계산해주는 것이다.

배운점

푸는 방법을 쉽게 생각하지 못했다. 자료구조와 DP의 문제보다는 문제를 해결하는 조건을 제대로 생각하지 못한 것 같다.

문제 접근 방법에 대해서 조금 더 배워야 할 것 같다.

GitHub

https://github.com/ryudonghun78/Problem_Solving/blob/master/Baekjoon_Algorithm/DP/1912.cpp

ryudonghun78/Problem_Solving