백준[ 16493 | Python ] 수익

문제

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

import sys
input = sys.stdin.readline

while True:
    N = int(input().rstrip()) 
    if N == 0:
        break
    dp = [int(input().rstrip()) for _ in range(N)]
    for i in range(1,N):
        dp[i] = max(dp[i],dp[i]+dp[i-1])#선택을 안하는 경우에는 그냥 값을 갱신하지 않고 전의 값을 불러오면된다.
    print(max(dp))

생각 & 정리

한동안 바빠 알고리즘 문제를 풀지 못하다가 다시 마음을 잡고 다시 준비하게 되었다.
이 전에 한창 풀고있던 DP문제를 다시 풀기로했는데, 모든 것이 새롭게 느껴져 실버2부터 다시 시작하기로 했다.
DP는 계산 과정에서의 결과를 기록하며 원하는 결과를 다시 계산에 이용하는데 메모이제이션을 이용한다. 물론 다른 방법도 있겠지만 원하는 결과를 선택하기 위해서 다른 값을 현재 선택한 값으로 갱신하는 방법이 기본인 것 같다.