[C++]백준 - 1912번 문제

1912번: 연속합 (acmicpc.net)

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보다 작거나 같은 정수이다.

 

 

출력

---

첫째 줄에 답을 출력한다.

 

 

---

 

생각해 볼 점

---

순서가 정해진 연속된 수를 합하여 연속합을 구할 것입니다.

 

생각해봅시다.

 

예를 들어, {3, -2, 5, -8, 11}를 입력 받았다고 생각해봅시다.

 

Sol(i)는 i번 째 까지의 연속합 중 가장 큰 값이라고 정의하겠습니다.

그리고, Sum(i)는 i까지의 연속합을 저장하고 있다고 합시다.

 

Sol(1) = 3, Sum(1) = 3 입니다.

 

Sol(2) = 3, Sum(2) = 1입니다.

 

Sol(3) = 6, Sum(3) = 6입니다.

 

즉, Sol(i)는 Sum(i)들 중 최댓 값을 갖고있습니다. 계속해보겠습니다.

 

Sol(4) = 6, Sum(4) = -2입니다.

 

Sum(4)가 음수가 되었습니다. 4번째까지의 합이 음수라면,

5번째 부터는 새로 연속합을 시작하는게 무조건 더 큽니다. 따라서, Sum이 음수가 되었다면, 초기화합니다.

 

Sol(5) = 11, Sum(5) = 11입니다.

 

따라서, 예시의 정답은 11이 됩니다.

 

이 규칙에 맞춰서 코딩하면 풀 수 있습니다.

 

 

 

코드

---

#include <iostream>
#include <algorithm>
using namespace std;

int main() 
{
    int N;
    scanf("%d", &N);

    //동적 할당
    int *dp = new int[N + 1];
    int *arr = new int[N + 1];
    fill_n(dp, N + 1, 0);
    
    //입력부
    int max_result = -1000;
    for(int i = 1; i < N + 1; i++)
    {
        scanf("%d", &arr[i]);
        
        //만약 i-1번째 연속합이 음수라면, 새로 연속합을 시작
        dp[i] = max(arr[i], dp[i - 1] + arr[i]);
        
        //여태까지의 연속 합 중 가장 큰 값을 저장
        if(max_result < dp[i]) max_result = dp[i];
    }
    
    //출력, 동적할당 해제
    printf("%d", max_result);
   
    delete[] dp;
    delete[] arr;    
	return 0;
}

 

그 외

---