[백준_1912] 연속합 ( PrefixSum, DP - 자바스크립트 )

문제

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

1912번: 연속합

 

How to Solve ?

 

문제의 핵심

 

주어진 배열에 있는 연속된 수 (부분 수열)를 통해 만들 수 있는 최대 값을 출력하라.

( 몇 개의 수가 연속 되는지는 상관이 없다 )

 

풀이 1 _ Prefix Sum ( 구간 합 )

 

부분 수열을 해결 하는 방법 중 대표적인 해결 방법으로써, 

 

1) 각 자리에서 얻을 수 있는 모든 값을 더한다

 

1번째 자리 : 0 

2번째 자리 : 1

3번째 자리 : 1 + 2..

 

2) 원하는 구간의 끝 - 원하는 구간의 시작 

 

저 값을 빼면 [start,end]의 구간의 합이 나온다. 우리가 찾는건 "구간 합"의 최대 이기 때문에 모든 값을 돌면서 구간합이 최대인 경우를 출력하면 된다.

 

구간 합으로 문제 풀이
function solve() {
  let prefix_sum = Array(n + 1).fill(0);
  let max = -Infinity;

  // 1
  for (let i = 1; i <= n; i++) {
    prefix_sum[i] = prefix_sum[i - 1] + nums[i - 1];
  }

  // 2
  for (let end = n - 1; end >= 0; end--) {
    for (let start = end - 1; start >= 0; start--) {
      let section = prefix_sum[end] - prefix_sum[start];

      if (max < section) {
        max = section;
      }
    }
  }
  console.log(max);
}

 

풀이 2 _ DP

 

이전까지의 값을 더하거나, 더하지 않는 값 중 더 큰 값을 자신의 자리에 저장하는 방식을 반복하여, 나온 결과 중 최대 값을 출력해준다.

function solve() {
  for (let i = 1; i < n; i++) {
    dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
  }

  console.log(Math.max(...dp));
}

 

요약 

 

특정 Idx에서 최댓값을 얻을 때는 구간 합을 이용하는 것보다 DP를 이용하는게 시간 단축에 용이하다.