[Baekjoon] 1912: 연속합

문제

 

풀이

내 풀이

import sys
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

dp = [0] * n
dp[0] = arr[0]
for i in range(1, len(arr)):
    dp[i] = max(dp[i-1] + arr[i], arr[i])

print(max(dp))

이 문제는 단순하게 생각하여 현재까지 합들보다 현재 값이 크면 시작점을 현재 인덱스로 바꾸면 해결되는 문제이다.

이 문제에선 다음을 고려하여 풀이를 진행하면 해결법이 생각날 것이다.

• 음수 값이 포함되어도 합이 최대 일 수 있다는 점
• 그렇지만 음수는 합에 영향을 준다는 점 (모두 0 이상인 수라면 전체 합이 최대이다)

한 번 다음 세 케이스를 생각해보자

1) 1 2 -2 5 6

2) 1 2 -3 5 6

3) 1 2 -4 5 6

1번 케이스의 경우 모든 수의 합이 최대 값이다.

2번 케이스의 경우 모든 수의 합, (5, 6)이 최대 값이다

3번 케이스의 경우 (5, 6)이 최대 값이다.

 

위 케이스를 보면 이전까지의 합이 음수인 경우, 0인 경우, 양수인 경우를 생각하면 해답이 나온다는 것을 확인할 수 있을 것이다.

 

회고

위 문제는 단순한 DP 문제였다.

첫 날에는 해답이 보이지 않아 생각 후에 다음 날에 풀이를 해보았더니 풀렸다.

실력이 조금씩 오르는 것 같지만 당일에 바로 풀이할 수 있는 실력이 되도록 열심히 풀어야겠다.