다이나믹 프로그래밍1 - 백준 1912번 연속합✨

www.acmicpc.net/problem/1912

1912번: 연속합

IDEA

 

연속된 수열의 최대 합 문제로 dp로 풀 수 있다. 

dp[i] 에는 배열 arr[i] 까지의 연속된 수의 합 중 최댓값을 저장하자.

sum이 음수가 될 때는 그 이후 값부터 새로시작하는 게 더 큰 값이다.

 

• sum 의 부호와 상관없이 계속 더할 때

arr	5	-7	2
sum	5	-2	0

• sum이 음수일 경우 새롭게 시작할 때 (sum = 0 초기화 후 새로운 arr 값 더해줌 )

arr	5	-7	2
sum	5	-2	2

 

👀점화식 

1. DP[1] 과 SUM을 ARR[1] 로 초기화 해준다. 
   
   
2. SUM이 0이상인 경우 SUM + ARR[I] 를 더해 업데이트해준다. 
   만약 0보다 작다면 SUM = ARR[I] 로 초기화해준다
   
   
3. SUM과 DP[I-1] (즉, 이전까지의 최대 합) 을 비교한다. 
   만약 SUM이 더 크다면 DP[I] = SUM으로 업데이트되고 더 작다면 DP[I] = DP[I-1] 이 된다. 

arr	10	-4	3	1	5	6	-35	12	21
dp	10	10	10	10	14	20	20	20	33

1 ) ARR = 10 일 때 , SUM = 10 , DP[1] = 10 

2 ) ARR = -4 일 때 , SUM = 6  < DP[1]= 10 이므로 DP[2] = 10

3) ARR = 3일 때, SUM = 9 < DP[2] = 10

4) ARR = 1일 때, SUM = 10 = DP[3] = 10

5) ARR = 5일 때, SUM = 14 > DP[4] = 10 이므로 DP[5] = 14

6) ARR = 6일 떄 , SUM = 20 > DP[5] = 14 이므로 DP[6] = 20

7) ARR = -35일 때, SUM = -15 > DP[6] = 20 이므로 DP[7] = 20

8) SUM = -35 음수이므로 다시 초기화 SUM = ARR[8] = 12 < DP[7] = 20 이므로 DP[8] = 12

9) ARR = 8일 때, SUM = 33 > DP[8] = 12 이므로 DP[9] = 33

  

 

CODE

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

int arr[100001];
int dp[100001];

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d" , & arr[i]);
	//dp 초기화 및 점화식 설정
	dp[1] = arr[1];
	int sum = arr[1];
	for (int i = 2; i <= n; i++) {
		if (sum < 0) sum = arr[i];
		else sum += arr[i];
		dp[i] = (dp[i - 1] >= sum ? dp[i - 1] : sum);
	}
	printf("%d", dp[n]);
}

 

남의 CODE

나보다 메모리도 절반이고 속도도 8ms인 사람의 코드를 봐보자.

 

나는 dp에 arr[i]까지의 연속된 부분수열의 최대합을 저장해두었다.

즉 dp[i] 값을 구할 떄 arr[i]가 사용되지 않았을 수도 있다는 뜻이다. 

 

하지만 이 분은 dp에 arr[i]를 사용했을 때 얻을 수 있는 부분수열의 최대합을 저장해두셨다. 

점화식은 max (dp[i-1] + arr[i] , arr[i]) :arr[i]번째가 연속된 수열의 일부일 때 혹은 연속된 수열의 시작일 때 중 최댓값

이렇게 되면 dp[n] 값이 최대가 아닐 수 있다.  그거 때문에 ans를 사용해서 dp의 최대값을 저장해두셨다.

#include <cstdio>
#include <algorithm>

using namespace std;
int arr[100001];
int dp[100001];
int main() {
    int n, i;
    int ans = 0;

    scanf("%d", &n);

    for (i = 0; i < n; i++) scanf("%d", &arr[i]);

    dp[0] = arr[0];
    ans = dp[0];

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

    printf("%d", ans);

    return 0;
}