[백준] 1912 연속합 (실버2) / DP

문제요약

나의 코드 및 설명

n = int(input())
num_list = [0] + list(map(int, input().split()))
dp = [0] * (n+1) #dp테이블에 연속된 수들의 합 저장(만약 연속된 수들의 합이 음수라면 0 저장)

ans = 0

for i in range(1, n+1): #dp테이블 채우기
    dp[i] = dp[i-1] + num_list[i] #dp[i](현재 인덱스)는 이전까지 저장된 합(dp[i-1] + 현재숫자(num_list[i])
    if dp[i] < 0: #만약 연속된 수들의 합이 음수가 된다면
        dp[i] = 0 #음수말고 그냥 안더하는 걸 선택. 0으로 갱신

if max(num_list[1:]) < 0: #수열들이 음수로만 구성되어 있다면,
    ans = max(num_list[1:]) #그냥 안더해보고, 수열들 중 가장 큰 값이 정답
else:
    ans = max(dp)

print(ans)

피드백

DP 알고리즘 연습을 위해 풀어본 문제. dp 테이블에 연속된 수들의 합을 저장한다. 이 때, 합이 음수가 된다면 초기값인 0으로 갱신한다. 

DP 문제를 풀어보다보니, DP 문제 풀이의 공통점을 체감할 수 있었다. DP 문제는 1. 규칙을 찾고, 2. dp 테이블을 그려보고, 3. 점화식을 구해서 구현하면 된다. 여러 문제를 풀어보면서 문제 풀이에 익숙해질 수 있도록 해야겠다.