[Python] 백준 #1912- 연속합

문제

---

 

1912번: 연속합

코드

---

My answer

import sys
input=sys.stdin.readline

n=int(input())
num=list(map(int,input().split()))
dp=[0]*n

for i in range(n):
    if(num[i]>=0):dp[i]=max(0,dp[i-1])+num[i]
    else:  
        if(dp[i-1]+num[i]>=0):
            dp[i]=dp[i-1]+num[i]
        else:
            dp[i]=num[i] 
print(max(dp))

Another answer

n = int(input())
m = list( map(int, input().split(' ')))
 
for i in range(1, n):
    m[i] = max(m[i], m[i] + m[i-1])
    
print(max(m))

풀이

---

우선 이번 문제도 dp로 해결하는 문제였다. 

나는 케이스를 조금 나눠서 생각했다.

1. 양수일 경우 무조건 더한다. (1을 더하든 100을 더하든 어쨌든 증가하기 때문)

2. 음수일 경우 지금까지 합에다가 음수를 더했을 때 0보다 크면 계속 더한다.

-> 왜냐하면 그만 더하면 어차피 0에서 다시 시작이기 때문에, 더해서 0보다 크면 계속 더하는게 이득이다. 

3. 지금 합에다가 음수를 더했는데, 0보다 작아질 경우 지금까지 값을 무시하고 그냥 음수값을 넣는다.

이런식으로 갱신하면서 진행하도록 짰다.

그런데 another answer을 보니 훨씬 간단했다. 

똑같이 갱신하면서 진행하되, 다음꺼랑 더한게 지금꺼보다 큰 것으로 갱신하면 됐다. 

백준 문제의 예시를 통해서 설명해보면,  num= [ 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 ] 일 때,

[ i = 1]  num[1] = max( -4, -4+ 10 = 6 ) -> num[1] = 6 

[ i = 2]  num[2] = max( 3, 3+6= 9) -> num[2]  = 9

[ i = 3]  num[3] = max( 1, 1+9= 10) -> num[3]  = 10

이런식으로 계속 반복하다보면 최종적으로 아래와 같이 갱신된다. 따라서 m 중에서 가장 큰 연속합 33이 정답이 된다. 

m = [10, 6, 9, 10, 15, 21, -14, 12, 33, 32]

 

혹시 잘 푼 것 같은데 계속 fail이 뜬다면, 아래 반례를 시도해보길..저도 이 반례 해결하다가 오류를 찾았습니다. 

30 2 -3 10 -6 -2 -4 -5 3 -9 3 8 -6 -6 4 6 -7 5 -7 3 4 10 0 -3 -6 6 -9 -7 -10 0 -2                                    ^^^^^^^^^^^^^^^^^^ 출력 10 정답 18