728x90 반응형 19121 [백준/Python] 1912 연속합 문제: https://www.acmicpc.net/problem/1912 사용 알고리즘: DP 입력첫째 줄에 정수 n(1 ≤ n ≤ 100,000)둘째 줄에는 n개의 정수로 이루어진 수열 (수는 -1,000 보다 크거나 같고, 1,000보다 작거나 같은 정수 n 개의 정수로 이루어진 임의의 수열에서 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. (단 수는 한 개 이상 선택해야 함)-> 부분합을 구하는 문제로 전형적인 dp 문제! 만약 dp 로 풀지 않는다면 이중 for 문을 써서 모든 [a, b] 구간합을 다 구해서 확인해야 한다. 이중 for 문을 써서 완전 탐색을 한다면 O(n^2) 의 Big-O 시간을 가지게 되고 문제에서 주어진 n 의 최대 값이 10만 이.. 2024. 6. 23. 이전 1 다음 728x90 반응형