목록백준13398번 (1)

HS_development_log

백준 13998번 - 연속합2 / Java

문제 https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1≤n≤100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 연속합에서 하나를 제거할 수 있다는 조건이 붙은 문제. 처음에는 하나를 제거할때 마다 모든 경우의 수를 계산해보려고 했다. 그러나 아래의 문제점이 발견해서 다른 해결법으로 풀었다. 1. 시간 복잡도를 O(N)에 해결할경우 메모리를 많이써야해서 메모리 초과 2. 시간복잡도를 O(N^2)에 해결할 경우 시간 초과. 그래서 k번째 수를 제거하는 연속 합일 경우 k-1번째까지의 연속합과 k+1부터의 연속합을 ..
Algorithm-백준/다이나믹 프로그래밍 2020. 1. 19. 22:52
이전 Prev 1 Next 다음