주어진 수열에서 합이 S 이상인 연속된 부분수열 중 최소 길이를 출력하는 문제입니다. 이 문제는 시간 제한이 빡센 문제로 시간 복잡도를 $O(N)$ 이하로 만들지 않으면 바로 시간 초과가 날 수 있습니다. 여기서 사용할 수 있는 조건으로 원소가 연속되어있다는 것과 원소가 자연수라는 것입니다. 연속된 원소로 구성된 부분수열은 총 $\frac{n(n+1)}{2}$개 존재하는데, 이것도 다 탐색할 필요가 없습니다. i번 원소로 시작하는 연속된 부분수열 중 길이가 x인 것이 만약 부분합이 S 이상이라면 길이가 x보다 큰 것은 탐색할 필요가 없어집니다. 어차피 최소 길이를 구하는 중이기 때문이기도 하고, 부분합이 현재 탐색중인 부분합보다 크기 때문입니다.
이 문제의 해결 방법에는 인덱스 두 개를 사용합니다. 하나는 부분 수열의 시작점, 나머지 하나는 끝점을 나타냅니다. 이제 부분합을 구하여 그 값이 S보다 크다면 시작점을, 작다면 끝점을 1씩 증가시킵니다. 그리고 S보다 클 때 두 점 사이의 거리를 구하여 그 최소값을 계속 저장합니다. 여기서 부분합이 S보다 클 때 시작점을 1 증가시키는 이유는 아래와 같습니다.
i에서 시작하는 부분수열 중 부분합이S보다 크거나 같은 부분수열의 최소 길이가x일 때,i+1에서 시작하여 길이가x-1인 수열의 부분합이S보다 크다면 마찬가지로i+1에서 시작하는 부분수열 중 부분합이S보다 크거나 같은 부분수열의 최소 길이는x-1이다. 그 이유는i+1에서 시작하여 길이가x-1보다 작은 수열의 부분합은 항상i에서 시작하여 길이가x보다 작은 수열의 부분합보다 작기 때문인데, 가정에 의해 이 값은 항상S보다 작다.
소스 코드
| 언어 | 코드 | 시간 | 비고 |
|---|---|---|---|
| C++ | 코드(Github) / 코드(백준) | 2021-02-19 23:25:39 |