[BOJ] 백준 13398번 : 연속합 2 (JAVA)

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 또, 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다)

 

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 수를 제거하지 않았을 때의 정답은 12+21인 33이 정답이 된다.

 

만약, -35를 제거한다면, 수열은 10, -4, 3, 1, 5, 6, 12, 21, -1이 되고, 여기서 정답은 10-4+3+1+5+6+12+21인 54가 된다.

 

 

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

 

 

출력

첫째 줄에 답을 출력한다.

 

 

풀이

연속 합 알고리즘과 다이나믹 프로그래밍을 이용하여 풀 수 있는 문제였습니다.

 

"1912번 연속합" 문제에서 업그레이드된 문제이기 때문에 아직 1912번을 풀지 않으신 분은 아래 포스팅을 참조하시길 바랍니다.

 

 

[BOJ] 백준 1912번 : 연속합 (JAVA)

 

 

1912번은 특정 수를 지우지 않고 단순히 최대 연속 합을 구하면 되지만, 이번 문제는 특정 수를 지울 수 있는 선택지가 있어서 까다로운 점이 있었습니다.

 

dp 배열을 1차원으로 설정하느냐, 2차원으로 설정하느냐에 따라 풀이 방법이 갈렸고, 저는 두 방식 모두 설명하려고 합니다.

 

 

1차원 DP 배열 풀이

오른쪽 방향으로의 연속 합을 구하는 dp1과 왼쪽 방향으로의 연속 합을 구하는 dp2 배열을 각각 정의합니다.

그리고 dp1 중 가장 큰 값을 ans에 할당합니다. 이것은 특정 수를 제거하지 않았을 경우 최대 연속 합을 의미합니다.

 

이제, dp1의 처음과 맨끝을 제외한 수를 하나 하나 제거해 보면서 ans보다 큰 값이 있는지 확인하면 됩니다.

이때, i번째 수를 제거하였을 경우, 최대 연속합은 dp1[i - 1] + dp2[i + 1] 로 구할 수 있습니다.

위 점화식은 아래 그림을 통하여 이해를 하실 수 있을 듯 합니다.

 

 

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드 - 풀이1

 

 

2차원 DP 배열 풀이

dp[i][j] : i는 특정 수, j는 수를 제거한 적이 있는지 여부

 

 

dp를 위와 같이 정의한 후, 수를 제거할 경우와 제거하지 않을 경우로 나눈 다음 bottom-up 방식을 수행하면 됩니다.

이제, j = 0일 때와 j = 1일 때를 나누어서 점화식을 정의해 보겠습니다.

 

 

1) j = 0

이 경우는 수를 제거하지 않는 케이스를 의미합니다. 따라서 1912번 문제에서 했던 것과 마찬가지로

dp[i][0] = max(dp[i - 1][0] + arr[i], arr[i]) 을 취하면 됩니다.

 

 

2) j = 1

이 경우는 특정 수를 제거하는 케이스를 의미합니다. 이 케이스는 또 2가지 경우로 분류할 수 있습니다.

 

첫 번째는 특정 수를 처음 제거하는 경우입니다.

이 때, dp[i][1] = dp[i - 1][0] 을 취하면 됩니다. i번째 수가 없어졌기때문에 이전 최대 연속합을 가져오는 것입니다.

 

두 번째는 특정 수 이전에 제거된 수가 있는 경우입니다.

이 때, dp[i][1] = dp[i - 1][1] + arr[i] 를 취해야 합니다. i번째 수를 제거하려고 했으나, 그 전에 제거된 수가 있을 경우에는 i번째 수를 지울 수 없습니다. 따라서 이전 최대 연속합에서 arr[i]를 추가로 더해야 합니다.

 

첫 번째 경우에는 dp[i - 1][0]을 가져왔지만, 두 번쨰 경우에는 dp[i - 1][1]을 가져온 점을 주의 깊게 보셔야 합니다.

결국, 이전에 어떤 수가 지워진 적이 있느냐 없느냐를 따지는게 중요했습니다.

 

정리하면, dp[i][1] = max(dp[i - 1][0], dp[i - 1][1] + arr[i]) 입니다.

 

 

이제, 필요한 점화식을 모두 얻어냈습니다. 이제 이 점화식을 이용하여 dp 배열을 초기화하고, 그 과정에서 가장 큰 값을 출력하면 끝입니다.

 

자세한 내용은 아래 소스코드를 참고하시길 바랍니다.

 

 

소스코드 - 풀이2

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.