[C] 백준 2559번 수열

김진웅·2023년 8월 13일

2559 2559번 C c언어 누적 합 백준 부분 합 수열 알고리즘

baekjoon-study

목록 보기

7/59

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

문제

매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다.

예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때,

3 -2 -4 -9 0 3 7 13 8 -3

모든 연속적인 이틀간의 온도의 합은 아래와 같다.

이때, 온도의 합이 가장 큰 값은 21이다.

또 다른 예로 위와 같은 온도가 주어졌을 때, 모든 연속적인 5일 간의 온도의 합은 아래와 같으며,

이때, 온도의 합이 가장 큰 값은 31이다.

매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다. 둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -100 이상 100 이하이다.

출력

첫째 줄에는 입력되는 온도의 수열에서 연속적인 K일의 온도의 합이 최대가 되는 값을 출력한다.

예제 입력 1

10 2
3 -2 -4 -9 0 3 7 13 8 -3

예제 출력 1

예제 입력 2

10 5
3 -2 -4 -9 0 3 7 13 8 -3

예제 출력 2

아이디어 스케치

누적 합을 이용하는 문제로 누적 합 알고리즘을 이용하지 않으면 시간 초과가 발생한다.
K의 입력 값에 따라 누적 합을 구하는 인덱스의 범위가 달라진다.
먼저 기본적인 누적 합 부터 구해놓고 이 누적 합을 이용하여 K의 값의 변화에 대응하게 설계하면 될 것 이다.

코드 분할 설명

 scanf("%d %d", &N, &K);

 arr = (int*)calloc(N, sizeof(int));
 SumArr = (int*)calloc(N, sizeof(int));			// 누적 합 배열

N과 K를 입력받은 후 N의 수만큼 arr과 sumArr을 동적할당

 for (int i = 0; i < N; i++) {
    scanf("%d", &arr[i]);
    if (i == 0)
        SumArr[i] = arr[i];
    else
        SumArr[i] = SumArr[i - 1] + arr[i]; // 누적 합 계산
}

누적 합을 구하여 SumArr에 저장하는 알고리즘

https://velog.io/@dnddl9456/C-%EB%B0%B1%EC%A4%80-11659%EB%B2%88-%EA%B5%AC%EA%B0%84-%ED%95%A9-%EA%B5%AC%ED%95%98%EA%B8%B0-4 이곳에서 설명했던 알고리즘 (참고)

 max = SumArr[K - 1]; // 처음 K 길이의 구간 합으로 초기화

// K 길이의 구간 합 중 최댓값 계산
for (int i = K; i < N; i++) {
    int intervalSum = SumArr[i] - SumArr[i - K]; // K 길이의 구간 합 계산

    if (intervalSum > max)      // max의 값보다 크면 max 값을 현재의 값으로 갱신
        max = intervalSum;
}

max를 처음 K 길이의 구간 합으로 초기화한 후 max보다 클 경우에 max를 갱신하는 알고리즘
K-1인 이유는 K=2 일 경우 SumArr[1] 즉 index 0~1에 해당하는 누적합이 저장되어 있기 때문에 주어진 범위에 -1을 해줘야 함.
이미 max에는 SumArr[K-1]의 값이 저장되어 있으므로 루프는 i=K부터 시작
SumArr[i] - SumArr[i - K] 이 코드는 구간 합을 구할 때 구해야 하는 범위의 누적합에서 구해야 하는 범위보다 작은 인덱스의 누적합을 빼는 코드로 현재 해당하는 범위의 누적합을 구하는 코드이다.

전체코드

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int N, K;
    int* arr;
    int* SumArr; // 누적 합 배열
    int max;

    scanf("%d %d", &N, &K);

    arr = (int*)calloc(N, sizeof(int));
    SumArr = (int*)calloc(N, sizeof(int));

    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
        if (i == 0)
            SumArr[i] = arr[i];
        else
            SumArr[i] = SumArr[i - 1] + arr[i]; // 누적 합 계산
    }

    max = SumArr[K - 1]; // 처음 K 길이의 구간 합으로 초기화

    // K 길이의 구간 합 중 최댓값 계산
    for (int i = K; i < N; i++) {
        int intervalSum = SumArr[i] - SumArr[i - K]; // K 길이의 구간 합 계산

        if (intervalSum > max)      // max의 값보다 크면 max 값을 현재의 값으로 갱신
            max = intervalSum;
    }

    printf("%d", max);

    free(arr);
    free(SumArr);

    return 0;
}