[백준] - 10211 maximum subarray

✅ 문제

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

1. 처음 풀이

• 누적합 문제라고 생각하니까 누적합 배열을 만들어야한다고 생각했다.
• 그래서 일단은 1<=j<=n 인 j까지의 합의 배열(누적합 배열) 을 만들고 나서 생각해보니 i가 무조건 1이 아니라는 것을 깨달았다.
• 그래서 다른 배열(resulttable)을 또 만들어서 거기서 최댓값을 구해야겠다고 생각했다.
• sum(i,j)를 풀었던 기억을 되살려서 모든 경우의 수를 다 한 후 최댓값을 구했다.

import sys
input=sys.stdin.readline

t=int(input())

for i in range(t):

    n=int(input())
    table=[0] + list(map(int, input().split()))

    sumtable=[0]
    resulttable=[0]
	
    # 누적합 구하기
    for j in range(1,n+1):
        sumtable.append(sumtable[j-1]+table[j])

    for k in range(1, n+1):
        for g in range(1, n+1):
            if k<=g :
                resulttable.append(sumtable[g]-sumtable[k-1]) 

    # print(resulttable)
    result=max(resulttable[1:])

    print(result)

✅ 물론 이 방법도 정답처리가 되었지만 시간복잡도가 높아 다른 사람들의 풀이를 찾아봤다.

✔️ 누적합 문제가 아니라 동적프로그래밍(dp) 문제였다.

• dp는 이전에도 참 어려웠는데,,
• 다른 사람들의 풀이를 봐도 잘 이해가 가지 않아서 유튜브로도 풀이 영상을 봤다.
  https://www.youtube.com/watch?v=0bqfTzpWySY

2. 보고 푼 풀이

import sys
input=sys.stdin.readline

for i in range(t):
    n=int(input())
    table=list(map(int, input().split()))

    dp=[0]*n
    dp[0]=table[0]

    for j in range(1, n):
        dp[j]=max(dp[j-1]+table[j],table[j])
    
    print(max(dp))

• 이전의 경로가 최적이었다면 뒤를 돌아보지 않는다.
• 계속 더하는 것이 좋은 방법인지, 아니면 j에서 다시 시작하는 것이 좋은지를 결정해서 나아간다.
• 무조건 연속된 값을 끼리 더해야한다는 특징을 잊지 말자.