https://www.acmicpc.net/problem/1912
1912번: 연속합
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
내 풀이
def solution():
n = int(input())
lis=list(map(int,input().split()))
for i in range(1,n):
#(print(f'lis[{i}]={lis[i]},lis[{i-1}]+lis[{i}]={lis[i-1]+lis[i]}'))
lis[i] = max(lis[i],lis[i-1]+lis[i])
#print(lis)
print(max(lis))
solution()일반적인 dp랑 다르게 굳이 memoization 리스트를 선언할 필요가 없다.
결국 핵심은 연속적인 수들의 합이기 때문이다.
다른사람의 풀이
'취준 > 백준' 카테고리의 다른 글
| 1238 - 파이썬 (0) | 2022.10.24 |
|---|---|
| 25755 - 파이썬 (0) | 2022.10.21 |
| 2589(보물섬) - 파이썬 (0) | 2022.09.02 |
| 16953(A -> B) - 파이썬 (0) | 2022.08.31 |
| 1389 - 파이썬 (0) | 2022.08.23 |