[python] 백준 1912 : 연속합

문제 링크

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

1912번: 연속합

 

풀이

처음에는 dp 테이블을

dp[n][m] : n부터 m까지의 합 으로 정의했고

dp[n][m] 이 dp[n+1][m] + 현재 위치의 값 이라는 걸 이용해서 푸는 문제인 줄 알았다..

length = int(input())
A = list(map(int,input().split()))
dp =[[-1001 for k in range(length)] for i in range(length)]

for i in range(0,length):
    dp[i][i] = A[i]

for i in range(length-1,-1,-1):
    for k in range(i+1, length):
        dp[i][k] = dp[i+1][k] + A[i]

print(max(map(max,dp)))

그런데 이 코드로 돌리면 예제는 정답이 나오는데

메모리 초과가 났다..

 

그래서 질문 게시판을 좀 뒤져보니깐

애초에 2차원 리스트로 푸는 문제가 아닌것 같아서

dp[n] : n을 포함하는 최대 연속값으로 새롭게 정의했다.

그렇게 되면 dp[n] 은 dp[n-1] + 현재 위치의 값이 오거나 

만약 dp[n-1] 이 지금 값보다 작다면, 그냥 현재 위치의 값이 될 것이다.

둘중 큰 수를 dp 에 채우고 dp에서 가장 큰 값을 출력하면 최대 연속합이 나온다.

 

length = int(input())
A = list(map(int,input().split()))
dp = [-1001] * length

dp[0] = A[0]

for i in range (1, length):
    if(dp[i-1] + A[i] > A[i]):
        dp[i] = dp[i-1] + A[i]
    else:
        dp[i] = A[i]

print(max(dp))