http://acm.pku.edu.cn/JudgeOnline/problem?id=3061
Description
A sequence of N positive integers (10 < N < 100 000), each of them less than or equal 10000, and a positive integer S (S < 100 000 000) are given. Write a program to find the minimal length of the subsequence of consecutive elements of the sequence, the sum of which is greater than or equal to S.
Input
The first line is the number of test cases. For each test case the program has to read the numbers N and S, separated by an interval, from the first line. The numbers of the sequence are given in the second line of the test case, separated by intervals. The input will finish with the end of file.
Output
For each the case the program has to print the result on separate line of the output file.if no answer, print 0.
Solving
시퀀스가 주어졌을 때 이 시퀀스의 연속된 서브시퀀스의 합이 s이상의 되는 서브시퀀스의 최소길이를 구하는 문제이다.
연속되는 서브시퀀스의 합을 그때그때 루프를 돌면서 구할 수도 있지만 이는 O(n^2)이 걸리는 매우 비용이 많이드는 작업이다. 특히 이 문제에서는 n이 100000까지 주어지기 때문에 O(n^2)의 해법은 너무 느리다.
연속인 서브시퀀스들의 합을 O(n)에 구하는 방법이 있는데 전체집합을 S라고 하고 집합의 원소의 수를 n이라고 하였을 때 A(k)를 첫번째 원소부터 k번째 원소(k<=n)까지의 합이라고 정의하면 A는 O(n)에 구할 수 있다. F(a, b)를 a번째 원소에서 b번째 원소까지의 합(연속된 서브시퀀스의합, 1<=a<=b<=n)이라 정의하면 F(a, b) = A(b) - A(a-1) 이 된다.
이제 최소의 길이를 구할 차례이다.
일감으로 이중루프를 돌면서 F(a,b) >= s 가 될때 b-a+1의 최소값을 구할 수는 있겠으나 위에서 언급했듯이 O(n^2)알고리즘은 이 문제를 풀기에 너무 느리다.
생각을 바꿔보자
길이가 t일때 F(k, k+t-1) >= s 인 k가 존재한다고 가정한다면 길이가 t+1일때는 F(k, k+t) >= s인 k가 당연히 존재하게 되므로 binary search를 통해 F(k, k+t-1) >=s를 만족하는 최소의 t를 O(log n)에 구할 수 있다(t <= n이므로) 그리고 각 이터레이션에서 F(k, k+t-1) >= s인 k를 구하는데 O(n)의 시간복잡도가 필요하므로(더 좋은 방법이 있는지는 모르겠다) O(n log n)의 알고리즘을 작성할 수 있다.
Solving
시퀀스가 주어졌을 때 이 시퀀스의 연속된 서브시퀀스의 합이 s이상의 되는 서브시퀀스의 최소길이를 구하는 문제이다.
연속되는 서브시퀀스의 합을 그때그때 루프를 돌면서 구할 수도 있지만 이는 O(n^2)이 걸리는 매우 비용이 많이드는 작업이다. 특히 이 문제에서는 n이 100000까지 주어지기 때문에 O(n^2)의 해법은 너무 느리다.
연속인 서브시퀀스들의 합을 O(n)에 구하는 방법이 있는데 전체집합을 S라고 하고 집합의 원소의 수를 n이라고 하였을 때 A(k)를 첫번째 원소부터 k번째 원소(k<=n)까지의 합이라고 정의하면 A는 O(n)에 구할 수 있다. F(a, b)를 a번째 원소에서 b번째 원소까지의 합(연속된 서브시퀀스의합, 1<=a<=b<=n)이라 정의하면 F(a, b) = A(b) - A(a-1) 이 된다.
이제 최소의 길이를 구할 차례이다.
일감으로 이중루프를 돌면서 F(a,b) >= s 가 될때 b-a+1의 최소값을 구할 수는 있겠으나 위에서 언급했듯이 O(n^2)알고리즘은 이 문제를 풀기에 너무 느리다.
생각을 바꿔보자
길이가 t일때 F(k, k+t-1) >= s 인 k가 존재한다고 가정한다면 길이가 t+1일때는 F(k, k+t) >= s인 k가 당연히 존재하게 되므로 binary search를 통해 F(k, k+t-1) >=s를 만족하는 최소의 t를 O(log n)에 구할 수 있다(t <= n이므로) 그리고 각 이터레이션에서 F(k, k+t-1) >= s인 k를 구하는데 O(n)의 시간복잡도가 필요하므로(더 좋은 방법이 있는지는 모르겠다) O(n log n)의 알고리즘을 작성할 수 있다.
'problem solving > Problem Solving' 카테고리의 다른 글
| Prime Path (0) | 2008.10.07 |
|---|---|
| Ugly Number (0) | 2008.10.06 |
| Center of symmetry (0) | 2008.10.02 |
| All in All (0) | 2008.10.02 |
| Risk (0) | 2008.10.02 |