[백준] 1912번 - 연속합 (DP) - 결과 포함
www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 앞선 문제들과 유사한 문제다보니 비교적 쉽게 해결했다. 연속해서 붙어있는 수열의 합이 가장 큰 것을 구하는 문제이다. 일단 연속이라고 했으니 앞에서부터 차례대로 숫자를 살펴본다. 만약에 다이나믹 프로그래밍, 메모를 이용하지 않는다면 모든 경우의 수를 계산해서 최댓값을 구할 것이다. 효율을 위해 메모를 이용한다. 메모에 적는 내용은 현재 보고 있는 숫자와 이전 결과에 현재 숫자를 더했을 때 둘 중에 더 큰 값이다. 예를 들..
개발 공부 (알고리즘)
2021. 4. 16. 21:20
