[백준]1912. 연속합.

문제설명

연속 합 중에서 최댓값을 구하라.

접근 방법

유튜브에 본 권오흠 교수님의 설명대로, DP문제를 풀 때 optimal substructure를 나타내는 순환식을 작성해야 한다.
사고 과정은 아래 이미지에 나타나 있는대로 접근하였다.

DP문제를 풀다보니 다음을 반드시 고려해야만하고, 이를 고려하면 문제의 구조를 잘 이해하게 된다.

• 단계를 어떤 변수로 설정하였는가? (이 문제에선 i,i+1,i+2..번째 수를 단계로 보았다.)
• i번째 단계에서 최적 값에 영향을 주는 변수는 무엇인가?
• i번째 단계의 최적 값은 이전에 구한 최적값으로 어떻게 표현할 수 있는가? 즉, optimal substructure을 구하라.
  • 1번째 2번째 단계의 최적 값을 푸는 건 간단하다.(이게 어렵다면 정말 어려운 문제다.)
    1. 앞서 고려한 두 질문에 대한 답들로 1번째 ,2번째 답을 풀어보자.
    2. 이제 그 답을 냈을 때 어떻게 생각했는지 글로 작성해보자
    3. 그럼 이것이 optimal substructure을 나타내는 지 생각해보자. 증명할 수 있다면 더할나위없이 완벽!
       • 완전탐색으로 접근한다면 답을 내기 쉬워진다. 이 문제에선 2번째 수열까지 연속합중 최대값을 구하는 문제라고 본다면 1번째 수열이 최대값인 경우, 1~2까지 의합이 최대인 경우, 2번째 값이 최대인 경우가 있다. 여기서 내가 단계를 i번째 수라고 정의하였고, 그 단계가 최적값에 영향을 주는 요인이므로 2번째까지의 합 중 최대는 f(2) = max(a_2,f(1)+a_2) 라 말할 수 있고, 1번째가 최대일 수 있으므로 답은 max(f(1),f(2))가 된다. 이렇게 순환적사고로, 완전탐색으로 접근하면 간편해진다. (이 문제에서는 dp가 문제의 최적 값이 아닌, 연속합일 때의 최적 값을 나타낸다. 이는 내가 어떻게 문제를 풀었는지 손으로 적다보면 알게 됨.)
    4. 코딩하여 답을 출력한다.
       • 간단 팁은 일반적으로 최적값은 배열로 dp 배열을 선언하고, 차수는 변수의 수만큼 선언한다. 이 문제에선 단계라는 변수 1개가 있으므로 1차원 dp를 선언한다. (knapsack 문제(배낭문제) 에서는 물건의 가치, 무게 2개의 변수가 있으므로 2차원 배열 선언) 그리고 i번째 인덱스엔 i번째 때의 최적값을 대입한다.

n = int(input())
nums = list(map(int,input().split()))
dp = [0 for _ in range(n)]

rst = nums[0] #초기 최대 값 설정
dp[0] = nums[0] #0번째 초기화. i-1번째를 볼 것이므로 0번째 초기화 후 1번째부터 풀이

for i in range(1,n):
    dp[i] = max(nums[i],nums[i]+dp[i-1])
    if dp[i]>rst:
        rst = dp[i]

print(rst)