363-B, *1100

Problem - 363B - Codeforces

문제

• $n(1 \leq n \leq 1.5\cdot 10^{5})$개의 수가 나열되어 있다
• 연속된 $k$개의 수의 합이 가장 작은부분은 어디인가?
• $O(nlog \ n)$ 정도 알고즘은 통과할 수 있다

 

$O(n)$

누적합을 저장하는 배열($acc$)을 만들면 $O(n)$
$$acc[i] - acc[i-k]$$
을 이용하여 $i-k+1$부터 $i$까지 원소의 합을 구할 수 있다
이제 모든 경우에 대해 값을 비교하여 최솟값을 구한다 $O(n-k)$

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
 
int h[200000];
int acc[200000];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int n, k;
    int tmp;
 
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> h[i];
 
    acc[1] = h[1];
    for(int i = 2; i <= n; i++) acc[i] = acc[i-1] + h[i];
 
    int minval = 20000000;
    int minval_ind = 1;
 
    for(int i = k; i <= n; i++) {
        if(minval > acc[i]-acc[i-k]){
            minval = acc[i]-acc[i-k];
            minval_ind = i-k+1;
        }
    }
 
    cout << minval_ind << endl;
 
    return 0;
}cs

$O(n-k)$

$s$를 배열$a$ 앞에서부터 $k$개의 수의 합이라 하자
$$s=\sum_{i=1}^{k}a_{i}$$
$s$에 $a[k+1]$를 더하고 $a[1]$을 빼면 2번째 수부터 $k+1$번째 수까지의 합을 구할 수 있다 $O(1)$
다시 $s$에 $a[k+2]$를 더하고 $a[2]$을 빼면 3번째 수부터 $k+2$번째 수까지의 합을 구할 수 있다 $O(1)$
같은방법으로 $n-k$번 반복한다 $O(n-k)$

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
 
int arr[200000] {};
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> arr[i];
 
    int s = accumulate(arr+1, arr+k+1, 0);
    int minval = s;
    int minval_ind = 1;
    for(int i = 1; i <= n-k; i++){
        s = s + arr[i+k] - arr[i];
        if(s < minval){
            minval = s;
            minval_ind = i+1;
        }
    }
 
    cout << minval_ind << endl;
 
    return 0;
}cs

시간초과

배열($a$)의 앞에서부터 매번 k개의 원소를 더한 값을 비교하는 brute force 를 시행하는 경우를 보자
$$a[i]+a[i+1]+\cdot \cdot \cdot + a[i+k-1] \quad i = 0, 1, 2, \cdot \cdot \cdot ,n-k$$
더하는데 $k$번의 연산이 필요하고, $n-k$번 비교를 하므로
$O(k(n-k))$의 수행시간이 드는데 $n=1.5\cdot 10^{5},\ k=n/2$ 이면
대략 $5.6 \cdot 10^{9}$ 번 연산을 하므로 시간초과이다