c언어 13398번 연속합 2 (백준)

#include <stdio.h>

int main(void)
{
	int n = 0;
	scanf("%d", &n); 
	
	int arr[n];
	int dp[n][2];
	int max = 0, max2 = 0; 
	
	for(int i = 0; i<n; i++) scanf("%d", &arr[i]);
	
	//1. 한 개 빼기 불가
    //dp을 이용해서 입력받은 값과 이전의 dp + 입력받은 값 중 더 큰것을 찾습니다.
    //max와 현재 dp을 비교해서 더 큰것을 max에 넣습니다.
	max = dp[0][0] = arr[0];
	for(int i=1; i<n; i++) {
		dp[i][0] = (arr[i] > arr[i] + dp[i-1][0]) ? arr[i] : arr[i] + dp[i-1][0];
		max = (max > dp[i][0]) ? max : dp[i][0];
	} 
	
	//2. 한 개 빼기 가능
    //dp2을 이용해서 입력받은 값과 이전의 dp2 + 입력받은 값 중 더 큰것을 찾습니다.
    //음수 일 경우 현재 dp2(이 값은 한개를 뺐을 수도 빼지 않았을수도 있는 값입니다.) 값과 이전의 dp(이 값은 한개를 빼지 않고 구한 값입니다) + 입력받은 값중 더 큰 것을 찾습니다.
    //양수인 경우 한개를 뺄 이유가 없으므로 생각하지 않습니다.
    //max와 현재 dp을 비교해서 더 큰것을 max에 넣습니다.
	dp[0][1] = arr[0];
	for(int i=1; i<n; i++) 
	{
		dp[i][1] = (arr[i] > arr[i] + dp[i-1][1]) ? arr[i] : arr[i] + dp[i-1][1];
		if(arr[i] < 0) dp[i][1] = (dp[i][1] > dp[i-1][0]) ? dp[i][1] : dp[i-1][0];
		max = (max > dp[i][1]) ? max : dp[i][1];
	}
	
	printf("%d", max);
	
	return 0;
}

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

13398번: 연속합 2

 

풀이 : 다이나믹 프로그래밍

 

13398번에서는 두가지 경우에서 연속합 중 최대를 구해야 합니다.

 

1. 반드시 연속한 합 중 최대

2. 한 개를 무시(제거)한 연속한 합 중 최대

 

 

 

반드시 연속한 합 중 최대는

 

1. 입력받은 값과 바로 전의 dp값 + 입력받은 값 중 더 큰 것을 지금의 dp값으로 하고

2. max와 지금의 dp 값중 더 큰 것을 max로 하면 됩니다.

 

한개를 무시한 연속한 합 중 최대는

 

일단 이에 대한 다이나믹 프로그래밍을 계산하는데 이용할 배열을 따로 준비해야 합니다.

이를 dp2로 명명하고 이어가면

 

1. 입력받은 값과 바로 전의 dp2값 + 입력받은 값 중 더 큰 것을 지금의 dp2값으로 하고

2. 음수인 경우 지금의 dp2값과 바로 이전의 dp값 + 입력받은 값 중 더 큰 것을 지금의 dp2값으로 하고

3. max와 지금의 dp값중 더 큰것을 max로 하면 됩니다.

 

여기서 반드시 연속한 합 중 최대를 구하는 부분과 다른 점은 바로 2. 입니다.

 

일단 음수인 경우에만 발생하는 이유는, 연속합의 최대를 구하는 것이기에, 음수가 아니라면 반드시 더하는 것이 연속합의 최대를 구하는 것이기 때문입니다.

 

또한 2. 에서 dp2가 아니라 dp을 사용하는 것은, dp값들은 한번도 어떠한 값들을 뺀 적이 없이 구해진 값이나,

dp2는 이미 한개를 무시했을 수도 있고 아닐 수도 있기 때문입니다. 즉 dp2을 이용해버리면 한개가 아닌 두개이상을 무시한 연속합의 최대를 구하게 될 수도 있습니다.