[Baekjoon - 24759] Slide Count

난이도: Silver I

 

태그

• Two Pointer
• Prefix Sum → Imos Method
• Simulation

 

풀이

1. Window 찾기

사실 문제에서 알고리즘을 다 알려줬기 때문에, 그대로 해주면 됩니다.

다만 \( w_s + \ldots + w_{e+1} \)을 계속 일일히 계산할 수는 없으므로,

\( w_s + \ldots + w_e \)를 잘 들고 다니거나 / Prefix Sum을 사용해주면 됩니다.

 

2. Window 속의 원소들 빠르게 세기

\( [s, e] \) 구간의 Window를 찾았다고 해봅시다.

가장 먼저 떠오르는 생각은 \( s \le i \le e \)인 모든 \( i \)에 대해 등장 횟수를 1씩 더하는 거지만, 이대로면 TLE가 납니다.

 

대신에, imos법을 사용해봅시다.

\( c_{s} \)에 1을 더하고, \( c_{e+1} \)에 1을 뺀 뒤, 모든 계산이 끝난 뒤 누적합을 계산하면 우리가 원하는 답을 알 수 있게 됩니다.

 

3. 코드

int arr[100020];
int res[100020];
 
void Main(){
    int n, k; cin >> n >> k;
    for (int i = 1; i <= n; i++){ cin >> arr[i]; }
    int st = 1, ed = 1;
    int sum = arr[st]; while (st <= n){
        //cout << st << ' ' << ed << endl;
        res[st] += 1; res[ed+1] -= 1;
        if (ed >= n){ sum -= arr[st]; st += 1; }
        else if (sum+arr[ed+1] > k){ sum -= arr[st]; st += 1; }
        else{ ed += 1; sum += arr[ed]; }
    }
    for (int i = 1; i <= n; i++){ res[i] += res[i-1]; }
    for (int i = 1; i <= n; i++){ cout << res[i] << endl; }
}