[백준 1912] 연속 합 - python (solved.ac - 실버 2)

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

1912번: 연속합

풀이

문제를 보았을때 알수있는 힌트

연속된 몇개의 수를 더해서 큰 합을 구하는 문제이다. 입력을 통해 n이 최대 10만인것을 보아 n^2은 하면 안될것으로보인다. 그렇다면 dp(다이나믹 프로그래밍)문제일 것이라고 생각을하고 접근하였다.

dp를 담을 리스트를 생성하고 임의의 수열에 처음부터 하나씩 비교하며 큰값을 dp에 작성하며 접근한다.

예제 문제를 통해 처음에 있는 10은 dp[0]에 10을 입력하고 이어서 -4를 계산하면 10-4=6과 -4중에 큰 6을 dp에 넣는다. 이것을 반복하며 풀면 10 6 9 10 15 22 -13 12 33 32 가 나오는데 이때 제일 큰 33을 출력하면 끝이 난다.

 

import sys
input= sys.stdin.readline

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

for i in range(1,n):
    dp[i]=max(node[i],dp[i-1]+node[i])

print(max(dp))

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon1912.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리