백준/동적프로그래밍49 백준 c++ 13398 - 연속합 2 https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 필자 처음 사고과정 : DP문제가 이 문제의 해결 KEY다 -> D[idx] 마다 최댓값을 저장하려 했지만 문제의 조건중에 자유롭게 하나의 수를 제거할 수 있다. 라는 이유로 이 방식은 포기했다. 해결과정 : 이 문제의 핵심은 위의 그림처럼 X표시 되는 모든 구간을 조사하여 최댓값이 되는 값을 구해야 되는 문제다. 이러한 이유로 L벡터와 R벡터를 만들었다. L 벡터에는 왼쪽부터 시작하여 배열의 마지막.. 2024. 2. 13. 이전 1 ··· 10 11 12 13 다음