[백준/C] 11659번 구간 합 구하기 4 - 슬라이딩 윈도우 알고리즘

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

슬라이딩 윈도우 알고리즘을 사용한다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#define MAX_STRING_SIZE 100001


int main() {
    int n, m; // n: 숫자 개수, m: 구간 개수
    int a, b; // a, b: 구간 끝
    int i; // 반복
    int arr[MAX_STRING_SIZE];
    arr[0] = 0; // 이 코드 없어도 결과 정상적인 이유가 뭘까...

    scanf("%d %d", &n, &m);

    for (i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
        arr[i] += arr[i - 1];
    }

    for (i = 0; i < m; i++) {
        scanf("%d %d", &a, &b);
        printf("%d\n", arr[b] - arr[a - 1]);
    }

    return 0;
}

 

 

 

 

 

 

 

 

 

---

https://www.youtube.com/watch?v=uH9VJRIpIDY

​

​

https://velog.io/@zwon/%EC%8A%AC%EB%9D%BC%EC%9D%B4%EB%94%A9-%EC%9C%88%EB%8F%84%EC%9A%B0Sliding-Window

 

---

아래는 시간초과 코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#define MAX_STRING_SIZE 100001



int main() {
    int n, m; // n은 입력할 숫자 개수/ m은 숫자 구간 개수
    int i, k; // 반복
    int a[MAX_STRING_SIZE];
    int left, right, sum = 0;

    scanf("%d%d", &n, &m);
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    
    for (i = 0; i < m; i++) {
        scanf("%d%d", &left, &right);
        for (k = left-1; k <= right-1; k++) {
            sum += a[k];
        }
        printf("%d\n", sum);
        sum = 0; // sum 초기화
    }
}

​