[백준 13398번 연속합 2 - node.js] [알고리즘 기초 1/2]

https://www.acmicpc.net/problem/13398

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보다 작거나 같은 정수이다.

 

출력

 

첫째 줄에 답을 출력한다.

 

예제 입출력

 

입력	출력
10 10 -4 3 1 5 6 -35 12 21 -1	54

 

풀이[node.js]

 

 

728x90

이번 문제는 연속합과 비슷한 형식인데요.

dp2가 추가되었다는 점만 다릅니다.

아래는 연속합 문제설명 링크입니다.

https://leylaoriduck.tistory.com/534?category=880546 

[백준 1912번 연속합 - node.js] [알고리즘 기초 1/2]

 

연속합에서 구했듯이, dp는 그대로 놔두고, 값을 삭제해야할 경우를 계산하는 dp2를 따로 구해봅니다.

dp2에서는 나 자신을 삭제하거나, 이전의 값이 삭제되어있는 경우엔 나 자신을 포함하는 경우 이 두가지가 있습니다.

 

10을 삭제한 경우엔, 0, 10을 삭제하지 않은 경우엔 10이므로, dp에서 최대값을 남겼듯이, dp2도 같은 방식으로 더 큰 값인 10을 살립니다. 이게 dp2[0] 값입니다.

-4에서 보자면, -4를 포함하는 경우엔, 이전 값이 삭제된 경우입니다.

이는 10이 삭제된 경우이므로, 10에서 -4를 뺀 6이 됩니다.

하지만 -4를 삭제한다면, 이전 값은 삭제하지 않은 경우이므로, dp[i-1]인 10이 -4를 삭제한 경우 최대값입니다.

 

3을 보면, 3을 포함하는 경우면 이전에 무슨 값을 삭제한 경우이므로, dp2(값을 제거한 최대값 배열)에서 이전 값을 가져와서 3을 더해주고, 3을 빼는 경우면, 이전에 삭제된 값이 없는 경우이므로, dp[i-1]인 6을 가져옵니다.

 

쉽게 말하자면, 나를 더하는 경우엔, 이전에 값이 삭제되있는 경우이므로, 이전에 값을 삭제한 수들 중 최대값들이 있는 dp2의 이전값에서 자기 자신을 더하는 것이고,

나를 빼는 경우엔, 이전에 값이 삭제되지 않았던 경우이므로, 이전에 값을 삭제한 적이 없는 수들 중 최대값들이 들어있는 dp에서 나 이전의 값을 가져와서 비교한 후, 최대값을 넣어주면 됩니다.

이렇게 비교하면, 이전의 값을 삭제하지 않았을 때의 값들과 나 자신, 딱 한가지 값을 삭제했을 때의 최대값들을 매번 비교하기 때문에, dp와 dp2의 값들 중 최대값을 구하면, 최종적으로 한가지 수를 제거했던, 안했던 간에 최대값을 구할 수 있는 것입니다.

 

var fs = require('fs');
var inputs = fs.readFileSync('/dev/stdin').toString().split('\n');
var cases = Number(inputs[0]);
inputs = inputs[1].split(' ').map(v=>Number(v));
var dp = [inputs[0]];
var dp2 = [inputs[0]];
for(var i=1; i<cases; i++){
    dp[i] = inputs[i] > inputs[i] + dp[i-1] ? inputs[i] : inputs[i] + dp[i-1];
}
for(var i=1; i<cases; i++){
    dp2[i] = dp[i-1] > inputs[i] + dp2[i-1] ? dp[i-1] : inputs[i] + dp2[i-1];
}
var dpMax = Math.max(...dp);
var dp2Max = Math.max(...dp2);
console.log(Math.max(dpMax, dp2Max));