#13398: 연속합 2
문제:
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: 연속합에서 풀었던 방식보다 더 효율적인 방식으로 푸는 방식을 배웠다. if문으로 크기를 비교하지 않고 바로 max를 써서 큰값을 배열에 저장해주는 방식이였다.
- 이 문제는 이차원 배열을 이용하여 탑다운 방식으로 푸는 문제이다. 2차원 배열을 사용하는 이유는 특정 값을 지웠냐 안지웠냐의 두가지 경우의 수를 나누기 위해서이다. 지웠을 경우에 또 다른 배열에 값들을 기록해야 되기 때문에 2차원 배열이 필요한 것이다.
-
우선 arr 배열에 모든 값을 저장해준다. 그 이후로 dp 0번째 배열에는 값이 없어야 되므로 최소값보다 1 낮은 -1001을 저장해준다. for문을 통해서 모든 값들을 한번씩 방문해준다. 방문 시 배열을 안지웠을 때 최대값을 저장해주며 배열을 지웠을 때 혹은 이전에 지웠을 때로 나누어서 최대값을 저장해준다. 그리고, 마지막으로 항상 최대값을 비교하여 answer에 최대값을 기록할 수 있도록 한다.
🧐 구현을 쉽게 정리하자면 max 함수로 이번 인덱스에서 지우는게 결과가 더 크다고 판단이 될 때마다 이전에 기록 된 ORGINAL에서 값을 같은 인덱스의 DELETE에 불러온 뒤 현재 인덱스의 입력값에 저장 된 값을 다음 지울 값이 나올 때까지 계속 저장 더하여 저장해준다. 다음 지우는 값이 나오는 기준은 여태까지 합한 DELETE에 있는 값이 이번에 arr에 저장 된 값이 너무 마이너스가 커서 더했을 때 이전 ORIGNAL 값보다 작게 나오면 더 이상 킵할 이유가 없기 때문에 미리 ORIGINAL에서 꾸준히 더해오던 값을 불러오는 것이다.
코드:
#include <iostream>
#define ORIGINAL 0
#define DELETE 1
using namespace std;
int main(){
int n, answer = -1001, arr[100001]={},dp[100001][2];
//입력
cin >> n;
for(int i = 1; i <= n; i++) cin >> arr[i];
//0번째 배열은 사용 안하므로 최소값보다 작게 초기화
dp[0][ORIGINAL] = dp[0][DELETE] = -1001;
//모든 배열 값 확인
for(int i = 1; i <= n; i++){
//배열을 지우지 않는 경우
dp[i][ORIGINAL] = max(arr[i]+dp[i-1][ORIGINAL], arr[i]);
//이번에 지우는 경우와 이전에 지웠을 경우 중 최대값 저장
dp[i][DELETE] = max(dp[i-1][ORIGINAL], dp[i-1][DELETE]+arr[i]);
//여태까지 나온 값과 이번에 나온 지웠을 때 값과 안지웠을 때 값의 최대값
answer = max(answer,max(dp[i][ORIGINAL], dp[i][DELETE]));
}
//출력
cout<<answer;
}
Leave a comment