[백준] No.13398 - 연속합2 (C++)

문제

www.acmicpc.net/problem/13398

13398번: 연속합 2

 

풀이

누적 합과도 연관된 DP문제.

연속합1 문제의 경우 해당 숫자를 합에 더하거나 해당 숫자에서 다시 연속 합 계산을 시작하는 두 경우를 비교하여 O(n)시간에 가장 큰 연속합을 구할 수 있다.

 

본 문제에서는 수열 중에서 한 숫자를 제외하거나 하지 않는 연속합들 중 최댓값을 찾아야 한다.

연속합1과는 다르게 2차원 배열 dp[100000][2]를 이용한다.

 

1. dp[i][0]에는 숫자가 제외되지 않은 경우를 저장한다.

i번째 수를 더한 경우(dp[i-1][0] + num)와 i번째부터 다시 시작하는 경우(num)을 비교하여 더 큰 수가 dp[i][0]이다.

dp[i][0] = max(dp[i-1][0] + temp_num, temp_num);

 

2. dp[i][0]에는 숫자가 제외된 경우를 저장한다.

i번째 수를 제외하여 연속합을 구하는 경우 dp[i-1][0]의 값을 그대로 가져온다.

제외하지 않는 경우, 이미 특정 수가 제외된 연속합의 최댓값 dp[i-1][1]에  i번째 수(num)을 더해준다.

dp[i][1] = max(dp[i-1][0], dp[i-1][1]+ temp_num);

 

최종적으로 1,2번 경우 중 더 큰 값을 max_num과 비교한다.

 

본 코드에서는 max_num은 for문에 포함되지 않는 dp[0][0]값으로 미리 초기화해 준다.

 

코드