[Python][DP] Q1912 연속합

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

 

 

연속된 수의 합의 최댓값을 구해야한다.

연속된 수의 합이므로 DP를 사용해야 할 것 같다!

---

1. 입력 : n(정수의 개수), arr(정수 배열)

import sys

n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

 

2. [DP] 계산 : 연속된 값을 더해 리스트에 저장

(1) 혼자 작성한 코드... (다른 풀이들과는 좀 달랐다)

total = arr.copy()
for idx in range(1, n):
    if total[idx-1] < 0 :
        total[idx] = arr[idx]
    else :
        total[idx] += total[idx-1]
print(max(total))

 

total[i]는 arr[i]와 그 앞선 값들과의 합이다.

연속한 수들의 최댓값을 구하려면, 음수에서 잘라 검사해야한다고 생각했다.

 

만약 total[i-1]이 음수라면, total[i] + total[i-1] < total[i] 가 된다.

음수라 더하면 그 값이 작아지므로, 그 경우엔 본래 값을 그대로 가지도록 했다.

 

(2) 다른 풀이 참고해 작성한 코드(이게 정석인 듯 하다)

total = arr.copy()
for idx in range(1, n):
    total[idx] = max(total[idx], total[idx]+total[idx-1])
print(max(total))

사실 로직은 같다.

음수가 더해지면 본래 값보다 작아진다는 점을 이용했는데,

이걸 조건문(내가 작성한 코드)가 아닌 max()함수를 사용한 것!

훨씬 깔끔하고 직관적이다.

---

전체 코드

import sys

n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

total = arr.copy()
for idx in range(1, n):
    total[idx] = max(total[idx], total[idx]+total[idx-1])
print(max(total))

 

굳이 arr.copy()로 배열을 따로 선언해 사용할 필요는 없지만,

입력값(본래 배열)과 결과값을 따로 확인하고 싶어서...