DP1 BOJ 1912 - 연속합(C++) https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 연속된 수에 대한 최대값이기 때문에 2가지만 고려함 1. 연속하지 않을 때 - 이전 값과 연속할 때 현재 값보다 작은 경우, 자기 자신을 가지고 감 - dp[i] > (dp[i-1] + dp[i]) 2. 연속할 때 - 이전 값과 연속할 때 현재 값보다 큰 경우, 연속합을 가지고 감 - dp[i] < (dp[i-1] + dp[i]) 순서대로 탐색하며 1, 2를 적용하고 최대값을 갱신 #include #i.. 2021. 10. 5. 이전 1 다음