백준 1912번 연속합 파이썬 풀이

Python

[Python] 백준 알고리즘 온라인 저지 1912 연속합

1912 연속합

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

1912번: 연속합

연속되는 수의 합이 가장 큰 값을 구하는 문제로 더해져 온 값과 비교하는 코드를 작성해야 한다.

 

알고리즘 분류

• 다이내믹 프로그래밍

---

소스코드

import sys
input = sys.stdin.readline

n = int(input())
nums = list(map(int, input().split()))
dp = [nums[0]]

for i in range(n-1):
    dp.append(max(dp[i]+nums[i+1], nums[i+1]))
print(max(dp))

---

풀이

첫 수를 dp에 넣고 for문을 이용해 다음 수와 dp를 더한 값과 다음 수를 비교하여 더 큰 수를 dp에 추가한다.

첫 번째 케이스 [10, -4, 3, 1, 5, 6, -35, 12, 21, -1]에서는 값들을 더해 오다가 -35에서 -14 vs 12를 비교한다.

12가 더 크므로 그냥 12를 넣고 21을 더한 값을 dp에 추가한다. 그 후 dp에서 가장 큰 값을 출력한다.

---

풀이 결과

1912 파이썬