[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번을 풀지 않으신 분은 아래 포스팅을 참조하시길 바랍니다.
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
지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.
'PS > 백준' 카테고리의 다른 글
[BOJ] 백준 4811번 : 알약 (JAVA) (0) | 2020.09.18 |
---|---|
[BOJ] 백준 2056번 : 작업 (JAVA) (0) | 2020.09.15 |
[BOJ] 백준 1912번 : 연속합 (JAVA) (0) | 2020.09.14 |
[BOJ] 백준 2302번 : 극장 좌석 (JAVA) (0) | 2020.09.13 |
[BOJ] 백준 10826번 : 피보나치 수 4 (JAVA) (0) | 2020.09.11 |
댓글