백준 파이썬 1912번 연속합

 

🚀접근하기

다이나믹 프로그래밍 문제를 풀 때마다 생각해야될 것이 점화식을 세우는 것과, dp배열을 따로 만들어 dp값들을 따로 저장해줄 수 있도록 배열을 하나 더 만드는 것이었는데, 이번 문제도 dp배열을 하나 더 만들어서 풀어주었다. 

 

처음 배열엔 입력했던 수들을 넣어주고, dp 배열을 하나 더 만들어서 dp배열의 이전 것(dp[i-1]) 과 arr배열의 현재 것(arr[i])을 더한 값과, arr배열의 현재 값(arr[i]) 중 더 큰 값을 dp배열의 현재값에 넣어주고, 

마지막엔 dp배열 중 가장 큰 max값을 고르면 이 값이 바로 구할 수 있는 합 중 가장 큰 합이 된다. 

 

ex) 예제 입력1
arr 10 -4 3 1  5  6  -35 12 21 -1
dp 10  6 9 10 15 21 -14 12 32 31

 

ex) 예제 입력 2

arr 2 1 -4 3 4 -4 6 5  -5 1   
dp 2 3 -1 3 7 3  9 14 11 12

🎉코드

n = int(input())
arr = list(map(int, input().split()))

dp = [0] * n
dp[0] = arr[0]
for i in range(1,n):
    dp[i] = max(arr[i], dp[i-1]+arr[i])
    
print(max(dp))

 

처음 배열엔 입력했던 수들을 넣어주고, dp 배열을 하나 더 만들어서 dp배열의 이전 것(dp[i-1]) 과 arr배열의 현재 것(arr[i])을 더한 값과, arr배열의 현재 값(arr[i]) 중 더 큰 값을 dp배열의 현재값에 넣어주고, 

마지막엔 dp배열 중 가장 큰 max값을 고르면 이 값이 바로 구할 수 있는 합 중 가장 큰 합이 된다. 

--> 아까 말했던 이것을 코드로 바꾸면 dp[i] = max(arr[i], dp[i-1]+arr[i])

💪다짐

다이나믹 프로그래밍 문제는 풀 수록 더 재밌는 것 같다. 

몇 가지 더 풀어보면서 확실히 마스터 해야겠다!