[백준(BOJ)] 1912번: 연속합 (Dynamic Programming, C++)

📝 문제풀이 과정

---

• 간단하게 생각했을 때, i번째 기준으로 연속되는 수를 i-1번째를 생각해서 풀어봤다.
• DP[i]: i번째에서 연속된 수의 가장 큰 합
• i-1번째를 포함하는 경우는, i번째 수(A[i])와 합했을 때 A[i]보다 커지는 경우이다. A[i] 기준 DP[i-1]을 더해서 커지지 않는다면 DP[i] = A[i]로 가져간다. 
• 따라서 DP[i] = A[i]로 초기화했을 때, 점화식 DP[i] = max(DP[i], DP[i-1] + A[i]) 가 된다.
• 마지막에 정답은 max_element()를 이용해서 DP 전체 범위에서 가장 큰 수를 출력했다.

 

 

💻 C++ 제출코드

---

#include <stdio.h>
#include <algorithm>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    int A[n] = {}; int DP[n] = {};

    for(int i=0; i<n; i++){
        int num; scanf("%d", &A[i]);
    }

    DP[0] = A[0];
    for(int i=1; i<n; i++){
        DP[i] = A[i];
        DP[i] = max(DP[i], DP[i-1]+A[i]);
    }
    
    printf("%d", *max_element(DP, DP+n));
}

 

 

👏 결과

---