백준 1912 JAVA (연속합)

DP 파트라는 것을 인지하고 문제에 접근하면 생각보다 쉽게 풀 수 있는 문제입니다. 우선 임의의 수열에서 연속적인 합의 최댓값을 구한다는 것이 가장 중요한 특성입니다. (1) 입력값이 한 개만 있을 경우 최댓값은 입력값 하나만 고려하면 됩니다. (2) 입력값이 두 개인 경우 최댓값은 arr[1]+arr[2]이 arr[2]보다 크면 됩니다. 이 결과를 dp[2]에 저장합니다. arr[1] + arr[2]이 arr[2]보다 작으면 연속합이 배열 요소보다 작다는 것을 의미하기 때문에 앞의 값은 버리고 arr[2]를 dp[2]에 저장하여 2번부터 계산합니다. 이후는 (2)번의 반복입니다. 앞에서 구한 두번째 배열 dp[2]와 arr[3]을 비교하여 dp[2]+arr[3]이 arr[3]보다 크면 dp[3]에 dp..
코딩/자바 백준 2021. 5. 15. 19:57
1