https://www.acmicpc.net/problem/1912
1912번: 연속합
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
n = int(input())
num = list(map(int,input().split()))
# n = 10
# num = [10, -4, 3, 1, 5, 6, -35, 12, 21, -1]
dp=[0]* (len(num))
dp[0] = num[0]
for i in range(1,len(num)):
dp[i] = max(num[i],dp[i-1]+num[i])
print(max(dp))이 문제 풀때 for 문 안에 있는 것이 중요
전거까지 더한거랑 지금꺼 더해서 크면 계속 더해서 넣어주고
만약에 지금꺼가 크면 지금꺼로 dp에 저장
반응형
'알고리즘 공부 > 다이나믹 프로그래밍' 카테고리의 다른 글
| [백준] 9095번 1, 2, 3 더하기 - 파이썬 (0) | 2022.05.02 |
|---|---|
| [백준] 12865번 평범한 배낭- 파이썬 (0) | 2022.02.26 |
| [백준] 9251번 LCS - 파이썬 (0) | 2021.08.09 |
| [백준] 14501번 퇴사 - 파이썬 (0) | 2021.08.08 |
| [백준] 2565번 전깃줄 - 파이썬 (0) | 2021.08.06 |