BOJ 1912 - 연속합

BOJ 1912 - 연속합

“연속합을 구하는 방법, 동적 계획”

BOJ 1912 - 연속합

문제 링크


#include <bits/stdc++.h>
using namespace std;

int N;
int arr[100010];
int dp[101010];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;

    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
        dp[i] = arr[i];
    }

    for (int i = 1; i <= N; i++) {
        dp[i] = max(dp[i], dp[i - 1] + arr[i]);
    }

    cout << *max_element(dp + 1, dp+N+1);
    return 0;
}

  • 처음에는 모든 연속합의 값을 전부 기록해야 할 것 같아서 이차원 배열(dp[101010][101010])을 만들어서 모든 연속합의 값을 기록했다. 물론 메모리 초과, 시간 초과가 발생했고, 두어시간 고민해봤지만 여기서 진일보 할수가 없었다…

  • 일차원 배열에 최대인 연속합의 값을 기록할 수 있는 방법이 있었다. 직전의 최대값을 기억해두고 다음 값을 기록하는 것이다. 처음 답안을 봤을 때는 잘 이해가 안갔는데, 잘 생각해보니 말이 된다.

for (int i = 1; i <= N; i++) {
    dp[i] = max(dp[i], dp[i - 1] + arr[i]);
}
  • dp 배열의 i번째 인덱스는, arr[i]로 끝나는 연속합의 최댓값이니 dp 배열의 max값을 찾으면 연속합의 최댓값이다.