연속합 2
[BOJ] 13398 연속합 2 (Pyhton / 파이썬)
[BOJ] 13398 연속합 2 (Pyhton / 파이썬)
2021.08.23🧷 문제 https://www.acmicpc.net/problem/13398 n개의 정수로 이루어진 임의의 수열이 주어질 때, 연속된 몇개의 수를 선택해서 구할 수 있는 합 중 가장 큰 값을 구하는 문제이다. (단, 수열에서 수를 하나 제거할 수 있다(제거하지 않아도 된다.)) 🛠 풀이 이 문제는 2차원의 DP table을 구성하여 해결할 수 있다. Step 1. 먼저 수열에서 수를 하나 제거했을 때 (dp[i][1])와 그렇지 않은 경우 (dp[i][0])로 나누어준다. dp[0][0], dp[0][1] 은 sequence[0]으로 초기화 해준다. Step 2. 1부터 n-1까지 for문을 돌면서 1. dp[i][0]은 아무런 원소를 제거하지 않았을 때를 비교하면 되므로, (이전까지의 연속합 + i번째..