[JavaScript/DP] 백준 실버 2 : 1912 - 연속합

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

1912번: 연속합

---

📌 작성한 코드 

// 1912
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Silver/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const N = Number(input[0]);
const list = input[1].split(" ").map(Number);

const dp = new Array(N);
let answer = list[0];
dp[0] = list[0];
for (let i = 1; i < N; i++) {
    dp[i] = Math.max(dp[i - 1] + list[i], list[i]);
    if (answer < dp[i]) answer = dp[i];
}

console.log(answer);

📌 설명 

dp를 사용해서 각 단계에 도달했을 때 최대값을 저장하여 최종적인 최대 연속합을 구하는 문제이다. 

 

정의 : dp[i] - 0 ~ i번째 숫자까지 도달했을 때 연속된 숫자의 최대값 

점화식 : dp[i] = max(dp[i-1] + list[i], list[i]) 

- 연속합을 구하는 경우에 할 수 있는 동작은 두가지가 존재한다. (1) 이전 합에 현재 숫자 더하기 (2) 이전 합을 버리고 현재부터 시작하기

- 이전에 구한 합에 현재 숫자를 더한게 더 크다면 더한 값을 저장하고, 작다면 현재부터 다시 더하기 시작하는 것이다. 

- 이때 dp의 마지막 요소에 최대값이 저장되어 있다는 보장이 없다. (각 단계별 최대값을 저장하는 것이지 전체 최대값을 저장하는 것이 아니기 떄문이다)

- 그래서 최대값은 변수를 사용해서 따로 저장하고 관리해준다. 

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

// output (dp array) 
[10, 6, 9, 10, 15, 21, -14, 12, 33, 32] // 마지막 요소가 최대값이 아님

 

✅ 성공