[백준] 1912번 연속합

March 14, 2021 ( last updated : March 14, 2021 )
dp 알고리즘 algorithm

https://github.com/sneakstarberry/

Abstract

[백준] 1912번 연속합

[백준] 1912번 연속합

백준 1912번 연속합

dp문제 중 하나입니다. 따라서 브루트포스 방식으로도 문제를 풀 수 있지만 제한 시간이 있기 때문에 그럴 수 없습니다. 그렇다면 최적화를 진행해야합니다. 해당 예시를 살펴 보겠습니다. 1, 2, 3, -3, 4 1부터 3까지 더하면 6입니다. 하지만 해당 값은 최대 값이 아닙니다. 뒤에 음수가 있어도 이후 4까지 더하면 7이 나오기 때문입니다. 해당 값을 구하는 공식을 만들어 보겠습니다.

dp[n] = dp[n] + dp[n-1]

해당 값(dp[n])의 연속합을 구하기 위해서는 계속해서 이전 값과 현재 값을 더한 값이 현재 값이 되어야합니다. 하지만 이로서는 연속합만 될 뿐 최대 값이 될 수는 없습니다. 따라서 최대 값이 되도록 하기 위해서는 조건을 추가해야하는데 2가지를 생각하면 됩니다.

  1. dp[i-1] > 0
    • 이전의 합이 음수라면 선택할 필요없이 현재부터 다시 선택하면 됩니다..
  2. dp[i] + dp[i-1] > 0
    • 이전의 합과 현재의 수를 더한 값이 음수라면 선택할 필요가 없습니다..

위의 두가지 규칙을 염두해 두고 구한 점화식을 이용해서 구현하면 다음과 같은 코드가 됩니다.

#include <iostream>
#include <vector>

using namespace std;

int N, dp[100001];

int main() {
  cin >> N;
  int max;

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

  max = dp[1];

  for (int i = 2; i <= N; i++) {
    if (dp[i - 1] > 0 && dp[i] + dp[i - 1] > 0) {
      dp[i] += dp[i - 1];
    }

    if (max < dp[i]) {
      max = dp[i];
    }
  }
  cout << max;
  return 0;
}

Originally published March 14, 2021
Latest update March 14, 2021

Related posts :

{# #}