2559. 수열

[예약 시간 오류] 230816 14:00 업로드 분 

 

[문제]

매일 아침 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일의 온도의 합이 최대가 되는 값을 출력한다.

 

[TC]

1.TC - Input

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

TC - output

21

2.TC - Input

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

TC - output

31

[접근]

여러 접근법을 사용해보았다.1. 수열을 뽑아내는 next_permutation 함수로 접근, 뽑아내는 수열이 일수 days 와 같은 사이즈를 갖는다면 합을 구해보는 것으로 진행=> next_permutation 이 제공하지않는 버전인지 멤버에 없는 함수라고해서 포기.

 

2. 아래 실패 코드로 접근, 단 방식은 여러가지로 진행 i 부터 days 까지 더하거나, days 까지 먼저 인덱스를 위치 시킨 후 0쪽으로 인덱스를 옮겨가면서 값을 구하는 방법=> 단, 어떻게 이동을 시키든, 최대 N*N, 즉 100억의 반복수를 줄이진 못함. 고로 타임 아웃

 

3. 누적합을 이용해, 구간쿼리 방식으로 구함.

1,2,3,4,5 배열이 주어졌을때 모든 수를 합하는 배열을 만듦. 

이전의 psum[i-1] 의 값을 이번input 인 arr[i] 에 더해서 누적합 배열을 만듦.

 

고로 여기서 3 ~ 5 값을 구하고자 했을때, psum[5] - psum[3] = 이 3 ~ 5의 값을 나타냄.

 

[코드] - C++

#include<iostream>
using namespace std;

int days;
int N;
int arr[100004] = { 0, };
int psum[100004] = { 0, };
int ret;
int input;

int main()
{
    cin >> N;
    cin >> days;
    ret = INT32_MIN;

    for (int i = 1; i <= N; ++i)
    {
        cin >> input;
        arr[i] = input;
    }

    psum[0] = 0;
    for (int i = 1; i <= N; ++i)
    {
        psum[i] = psum[i - 1] + arr[i];
    }

    for (int i = 0; i < N+1-days; ++i)
    {
        int sum = psum[i + days] - psum[i ];
        if (ret <= sum)
            ret = sum;
    }

    cout << ret;
    return 0;
}

 

 

[코드] - 실패 : C++

- 실패 사유 : 타임 아웃

#include<iostream>
using namespace std;

int days;
int N;
int arr[100004] = { 0, };
int psum[100004] = { 0, };
int ret;
int input;

int main()
{
    cin >> N;
    cin >> days;

    for (int i = 0; i < N; ++i)
    {
        cin >> input;
        arr[i] = input;
    }

    for (int i = 0; i < N- days +1 ; ++i)
    {
        for (int j = i; j < i + days; ++j)
        {
            psum[i] += arr[j];
        }
    }


    for (int i = 0; i <= days; ++i)
    {
        if (ret <= psum[i])
            ret = psum[i];
    }

    cout << ret;
    return 0;
}

[결과 및 시도]

[후기]

문제를 얼마 풀지 않았지만, 누적합을 모르면 전혀 풀수없는 문제였다.

1, 2번의 접근식으로 쉽게 풀 수 있다고 생각했는데 상당히 오랜시간과 집중력을 요하는 문제..

핵심인 누적합을 모르면 타임아웃을 빠져나갈 수 없었다.

 

오랜만에 풀어서 그런지 다시 감을 잡기는 좋은 문제였다.