백준 1912 연속합 문제풀이

문제 

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

1912번: 연속합

 

 

문제 접근 방식

완전탐색을 통해 문제를 접근할 수도 있겠으나 n 의 최댓값이 1e5이므로 제한 시간내에 동작하기는 어렵다. 다른 방식을 찾아야한다. 연속된 합을 저장하는 문제이기 때문에 항들간의 연관성이 있을 것 같아서 점화식을 찾는 방향으로 접근했다.

 

아래와 같이 d[ i ] 를 정의하여 d 를 구해놓고, 리스트 d에서의 최댓값을 구하면 수열내에서 가장 큰 연속합을 구할 수 있다.

 

d[ i ]= i 번째 수를 포함하여 만들 수 있는 연속합의 최댓값 

 

그럼 위와 같이 d[ i ] 를 정의했을 때, 점화식은 어떻게 되는가?

i 를 포함한 연속합의 최댓값은 { i -1 번째를 포함하는 최댓값에 i 번째 수를 더한 값 } 과 { i 번째 수 } 중 더 큰 값이라는 것을 알 수 있으며 이를 점화식으로 표현하면 아래와 같다

 

d[ i ] = max ( d[ i - 1 ] + nums[ i ], nums[ i ] )

 

이 점화식을 이용하여 모든 i 에 대해 d[i] 값을 구한 후, d[ i ]의 값 중 최댓값이 수열로 만들 수 있는 연속합의 최댓값이 된다.

 

시간 복잡도

for 문으로 전체 수열을 탐색하면 되기 때문에 O(n) 이며, n의 최댓값이 1e5 이므로 제한 시간 내에 동작한다.

 

 

코드

if __name__=='__main__':
    n=int(input())
    nums=list(map(int,input().split()))
    nums.insert(0,0)

    d=[0]*(n+1)

    # d[i] = i 번째 수를 포함하여 만들 수 있는 연속합의 최댓값
    for i in range(1,n+1):
        d[i]=max(nums[i],d[i-1]+nums[i])

    print(max(d[1:]))

 

 

회고

이웃한 항과의 연관성이 있는 것을 보고 dp 문제를 의심하였다.

dp 에 사용될 저장 데이터 d를 구하고자 하는 연속합의 최댓값과 연관되어 정의한 후 아래와 같은 점화식을 도출할 수 있었다.

 

d[ i ] = max( d[ i - 1] + nums[ i ], nums[ i ] )

 

이를 사용하여 모든 i 에 대한 d[ i ]를 구하고 이중 최댓값을 반환하여 전체 수열의 최댓값을 구하였다.