(Python/파이썬) 백준 1912번 - 연속합

문제출처: https://www.acmicpc.net/problem/1912

1912번: 연속합

1. 코드

n=int(input())
arr=list(map(int, input().split()))
sum=[arr[0]] #sum의 0번째 인덱스에 첫 문자 넣어줌
 
for i in range(len(arr)-1):
   sum.append(max(sum[i]+arr[i+1],arr[i+1])) 
   #sum의 i번째 인덱스와 새로운 숫자를 더한 값과
   #새로운 숫자를 비교했을 때 더 큰 값을 비교해서 리스트에 넣어줌
   
 
print(max(sum))

2. 해결과정

sum이라는 빈 리스트를 설정하고 0번째 인덱스에 arr의 첫 숫자를 넣어준다.

sum의 i번째 인덱스와 그 다음 새로운 숫자를 더한 값과, 새로운 숫자를 비교했을 때 더 큰 값을 sum 리스트에 추가한다. (음수값이 들어갈 수 있기 때문에)

마지막으로 sum리스트에서 가장 큰 값을 출력해주면 된다.

 

3. 느낀점

dp는 정말 점화식, 규칙만 찾으면 쉬운데..그 규칙 찾기가 넘 어려움 ㅜ