[쉬운 설명] 백준 1912번 연속합(파이썬, dp)

www.acmicpc.net/problem/1912

1912번: 연속합

 사실 이 문제는 여느 동적프로그래밍 문제에 비해서 너무 너무 쉬운 편이에요. 그렇다고 해도, 제 딴의 풀이를 공유해볼게요.

 

베이스 아이디어

 

1. 주어진 정수 리스트에 대한 리스트를 만든다( 흔히 말하는 dp list )

2. dp의 의미는 이 인덱스 입장에서 취할 수 있는 최대입니다.
*  여기가 중요한데요.
* 만약, 이 번 인덱스에 주어진 수에 의해서, 이전 인덱스까지의 dp를 감소하게 한다면, 그 이전 인덱스까지의 결과가 잠재적으로 최대일 수 있습        니다. 그렇기 때문에, results라는 "잠재적인 최대 부분합" 리스트를 만들어, 그 후보값을 그때 그때 저장해둘 것입니다.
* 하지만, 만약, 이전 인덱스의 dp값( 최대 부분합 )에 대해서, 이번 인덱스에서 그것을 감소하게 하지 않는다면, 즉, 이번 인덱스의 수가 0보다 크거나 같다면, 굳이 이전 인덱스 dp값을 저장할 필요가 없겠죠.

3. 이전에 비해 감소할 때마다 그때 그때 저장해둔 "잠재적인 최대 부분 합" 리스트에, 역시 최대 부분합이 될 가능성이 있는 dp어레이의 마지막 값을    추가해 줍니다. 왜 이걸 또 넣냐구요? 왜냐면, 저희가 잠재적인 최대 부분 합들을 results에 추가한 타이밍이, "이번 인덱스 수 때문에, 이전 인덱스        까지의 최대 부분합이 감소했을 때" 였기 때문이에요. 만약 마지막 부분에 주어진 수들이 계속 증가하거나, 엄밀히 말하면, 감소하지만 않았더라면,      dp[-1] 또한 잠재적인 최대 부분합이 될 수 있겠죠?? 맞죠??

4. print( max( results ) )

 

코드는 다음과 같아요 !!

n = int( input() )
lst = []

string = input()
lst = [ int(i) for i in string.split(" ") ]

#
dp = [0] * len(lst)
dp[0] = lst[0]

#
results = []

# 
for idx in range(1, n) : 
    
    #
    opt3 = dp[idx-1]
    
    #
    opt1 = dp[idx-1] + lst[idx]
    opt2 = lst[idx]
    
    #
    if opt3 > opt1 and opt3 > opt2 :
        results.append( opt3 )
        dp[idx] = max( opt1, opt2 )
    else : 
        dp[idx] = max( opt1, opt2 )

#
results.append( dp[-1] )

#
print( max(results) )

 

매우 비효율적인 거 같다 하시는 분들은,

따끔한 지적을 댓글에 써주세요 !!!!!! 

 

감사히 듣겠습니다