[BOJ] 1912. 연속합(DP, 누적합)

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

생각보다 단순한(?) 문제다.

DP[N]은 N까지의 수열에서 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합이라고 정의하자.

여기서 DP[N]은 

1. 연속된 수에 포함될 경우

2. 연속된 수에 포함되지 않을 경우

로 나뉠 수 있다.

연속된 수에 포함될 경우와 포함되지 않을 경우에서 가장 큰 값이 DP[i]가 된다.

DP[i] = max(DP[i-1]+A[i], A[i])

수열이 아래와 같을 때,

10 -4 3 1 5 6 -35 12 21 -1

A[]는 수열을 저장하고 있다.

dp[]는 최정적으로 아래와 같은 결과를 갖는다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

#include <cstdio> #include <algorithm> using namespace std;   int A[100001], DP[100001];    int main(void) {     int n, i, res;     //freopen("input.txt", "rt", stdin);     scanf("%d", &n);     for (i = 1; i <= n; i++) {         scanf("%d", &A[i]);         if (i == 1) res = A[i];           DP[i] = max(DP[i - 1] + A[i], A[i]);                  if (DP[i] > res)             res = DP[i];     }       printf("%d\n", res);     return 0; } Colored by Color Scripter

cs

line 12~20) 입력과 동시에 처리

line 14) 초기 res에 A[1]을 저장

line 16) 점화식 적용!!

line 18) 가장 큰 합을 저장

#. Other Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

#include <cstdio> #include <algorithm> using namespace std;   int main(void) {     int prev = 0, res = 0, dp = 0;     int n, i, a;     //freopen("input.txt", "rt", stdin);     scanf("%d", &n);     for (i = 1; i <= n; i++) {         scanf("%d", &a);         if (i == 1) res = a;           if (prev + a > a) {             dp = prev + a;             prev = dp;         }         else {             dp = a;             prev = a;         }                  if (dp > res)             res = dp;     }       printf("%d\n", res);     return 0; } Colored by Color Scripter

cs

로직을 이해했다면 최적화를 할 수 있다.

배열을 사용하지 않고, prev, a, dp 변수로만 문제를 해결할 수 있다.

변수 a는 입력된 정수A[i],

변수 prev는 DP[i-1],

변수 dp는 DP[i] 를 의미한다.