백준 1912: 연속합 - javascript(dp)

문제 출처 

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

1912번: 연속합

문제

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

예제 입력 1 복사

10
10 -4 3 1 5 6 -35 12 21 -1

예제 출력 1 복사

33

예제 입력 2 복사

10
2 1 -4 3 4 -4 6 5 -5 1

예제 출력 2 복사

14

예제 입력 3 복사

5
-1 -2 -3 -4 -5

예제 출력 3 복사

-1

 

문제 풀이 힌트 

전형적인 dp 문제~~~ 

dp 빈배열 생성후, 계속 최적의 선택을 할 것이다. 

언제나 그랬듯, 뒤에서부터 생각하자. 

 

`이전의 것과 더했을 때,`

이전의 것들과 더하는게 좋을지vs 현재부터 다시 시작하는게 좋을지 

비교를 한다. 

 

만약, 

이전의 것들과 더하는게 좋으면 dp[i]에 `dp[i-1] + 현재 값`을 채운다 . 

현재부터 다시 시작하는게 좋다면, dp[i]에 `현재값`을 채운다. 

 

문제 풀이 코드 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const N = Number(input[0]); 
const arr = input[1].split(' ').map(v => +v); 
let dp = new Array(N).fill(0); //빈배열 생성
dp[0] = arr[0]; //dp[0]은 이전값이 없다. 
for(let i=1; i<N; i++){
    dp[i] =  arr[i] > dp[i-1] + arr[i] ? arr[i] : arr[i] + dp[i-1]; 
}
console.log(Math.max(...dp)); //가장 큰 값 출력

Only 문제 풀이 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const N = Number(input[0]); 
const arr = input[1].split(' ').map(v => +v); 
let dp = new Array(N).fill(0); 
dp[0] = arr[0]; 
for(let i=1; i<N; i++){
    dp[i] =  arr[i] > dp[i-1] + arr[i] ? arr[i] : arr[i] + dp[i-1]; 
}
console.log(Math.max(...dp));

 

알고가는 ppoint) 

01.대괄호 때문에 틀린상황:  Math.max([...dp])=>  Math.max(...dp);

=> 스프레드 연산자로 대괄호를 풀어준건데 왜 또 대괄호를 씌우냐?