[백준] 1912. 연속합 풀이 / Python, JavaScript

1912번: 연속합

 

1912. 연속합 풀이

문제해결 아이디어는 다음과 같습니다.

1. 주어진 수열의 값들을 하나씩 순회한다.

2. 순회하는 값들을 현재값으로 축적한다.

3. 현재값이 증가할 경우 현재까지의 최댓값을 갱신한다.

4. 현재까지의 최댓값보다 더 큰 값이 발견되면 그 값을 현재값과 최댓값으로 새로 갱신한다.

 

처음 풀이 시 DP를 사용하지는 않았지만 문제 유형이 DP이므로 DP를 이용한 풀이방식도 함께 올립니다. 접근 방식은 동일하며 DP를 사용했을 때 코드가 더 간결하고 속도가 미세하지만 약간 더 빨랐습니다.

 

점화식은 아래와 같습니다.

V는 현재 순회중인 값. 테이블[i]는 인덱스 i까지의 최대 연속합
테이블[i] = max(V, 테이블[i - 1] + V)

 

작성코드 (Python)

import sys
input = sys.stdin.readline

n = int(input())
numbers = list(map(int, input().split()))
n_max = curr = numbers[0]

for i in range(1, n):
    curr += numbers[i]
    if curr > n_max:
        n_max = curr
    if numbers[i] > curr:
        n_max = max(n_max, numbers[i])
        curr = numbers[i]
print(n_max)

# DP
import sys 
input = sys.stdin.readline

n = int(input())
numbers = list(map(int, input().split()))
table = [numbers[0]] + [0] * (n - 1)

for i in range(1, n):
    table[i] = max(numbers[i], table[i - 1] + numbers[i])
print(max(table))

작성코드 (JavaScript)

function solution(n, numbers) {
  let [curr, nMax] = [numbers[0], numbers[0]];
  for (let i = 1; i < n; i += 1) {
    curr += numbers[i];
    if (curr > nMax) nMax = curr;
    if (numbers[i] > curr) {
      nMax = Math.max(nMax, numbers[i]);
      curr = numbers[i];
    }
  }
  return nMax;
}
solution(10, [2, 1, -4, 3, 4, -4, 6, 5, -5, 1])

// DP
function solution(n, numbers) {
  const table = Array(n).fill(0);
  table[0] = numbers[0];
  for (let i = 1; i < n; i += 1) {
    table[i] = Math.max(numbers[i], table[i - 1] + numbers[i]);
  }
  return Math.max(...table);
}
solution(10, [2, 1, -4, 3, 4, -4, 6, 5, -5, 1])