[백준/C] 2559번 수열 (슬라이딩 윈도우, 누적합)

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

2559번: 수열

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <limits.h>
#define MAX_ARRY_SIZE 100001
#define MAX(x,y) ( ((x) > (y)) ? (x):(y) )

int main(void) {
	int a, b; // a: 온도 개수,  b: 연속적인 b일
    int i, k; // 반복
	int t; // 온도 
	int sum[MAX_ARRY_SIZE] = { 0, }, max = INT_MIN;

    scanf("%d%d", &a, &b);

	// 누적합: 슬라이딩 윈도우
	for (i = 1; i <= a; i++) {
		scanf("%d", &t);
		sum[i] = sum[i - 1] + t;
	}
	for (i = b; i <= a; i++) {
		max = MAX(max, sum[i] - sum[i - b]);
	}

	printf("%d", max);
    return 0;

}

 

 

예) a = 7 , b = 3

a

b

c

d

e

f

g

sum[0]	0
sum[1]	a
sum[2]	a + b
sum[3]	a + b + c
sum[4]	a + b + c + d
sum[5]	a + b + c + d + e
sum[6]	a + b + c + d + e + f
sum[7]	a + b + c + d + e + f + g

​

i	sum[i] - sum[i-b]	sum[i] - sum[i-b]
3	sum[3] - sum[0]	a + b + c
4	sum[4] - sum[1]	b + c + d
5	sum[5] - sum[2]	c + d + e
6	sum[6] - sum[3]	d + e + f
7	sum[7] - sum[4]	e + f + g

---

다른 방법

---

아래는 시간 초과된 코드

억지로 생각 쥐어짜서 코드 짰음 크크카카커캬커ㅑ커

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <limits.h>
#define MAX 100001

int main(void) {
    int a, b, max = INT_MIN; // a: 온도 개수,  b: 연속적인 b일
    int i, k; // 반복
    int t[MAX]; // 온도 저장 배열
    int sum[MAX] = { 0, };

    scanf("%d%d", &a, &b);

    for (i = 0; i < a; i++) {
        scanf("%d", &t[i]);
    }
    // 누적합 배열 만들기
    for (i = 0; i <= a - b; i++) {
        for (k = 0; k < b; k++) {
            sum[i] += t[i + k];
        }
    }

    for (i = 0; i <= a - b; i++)
        if (sum[i] > max) max = sum[i];


    printf("%d", max);
    return 0;

}