[백준/C++] 알고리즘 1912번 - 연속합

안녕하세요! 테크지니어22입니다.

오늘은 백준 알고리즘 1912번 - 연속합을 풀어보도록 하겠습니다.

 

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

1912번: 연속합

 

[문제 접근]

시간 제한은 1초이고 n의 범위가 10만이기 때문에 완전탐색은 불가능합니다. 연속 합을 구하는 거여서 투 포인터로도 O(N)으로 줄이기 어렵다고 판단했습니다. 그럼 마지막으로 떠오르는 건 다이나믹 프로그래밍입니다. 그런데 아직 다이나믹 프로그래밍에 익숙하지 않아서 정의를 내리기가 무척이나 어려웠습니다. 결국 바킹독님 해설을 참고하여 문제에 접근했습니다.

d[i] : i번째 항으로 끝나는 연속합 중 최대 라고 정의를 했습니다.

 

[풀이 전략]

1. d[0] = arr[0]으로 초기화 합니다.

2. for문을 돌면서 d[i] = max(d[i-1]+ arr[i], arr[i]) 점화식을 이용하여 dp배열을 채웁니다.

3. dp 배열 중에서 값이 가장 큰 값이 연속합의 최대이므로 출력합니다.

 

[코드]

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


int arr[100'001] ;
int dp[100'001];
int n ; 
int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    cin >> n ;
    for(int i = 0 ; i < n ; i++) cin>> arr[i];
    
    dp[0] = arr[0];
    
    for(int i = 1 ; i < n ; i++){
        dp[i] = max(arr[i], dp[i-1]+arr[i]);
    }

    cout << *max_element(dp ,dp + n);
 
}

 

[배울 점]

- 다이나믹 프로그래밍 잘 모를 때는 일단 1차원 배열 정의 내리고, 안되면 2차원 배열 정의 내리기. ->  연습이 많이 필요함.