수열

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

#include <iostream>
#include <vector>

using namespace std;

int n, k;
vector<int> v;
int Max = -200000;
int main()
{
    cin >> n >> k;
    v.resize(n, 0);
    for (int i = 0; i < n; i++)
        cin >> v[i];

    for (int i = 0; i <= n - k; i++)
    {
        int temp{};
        for (int j = i; j < k+i; j++)
        {
            temp += v[j];
        }
        Max = max(Max, temp);
    }

    cout << Max << endl;
}

• 연속된 날짜에 온도를 더해 가장 큰 온도를 구하는 문제
• vector에 온도를 저장하고 연속된 날짜의 온도를 더해줘야한다
• 연속된 날짜의 온도 합을 구하기 위해 for문을 통해 반복할 것인데 규칙을 생각해보자
• 연속된 날짜가 2이면 덧셈을 한 값의 갯수는 9개, 3이면 8개, 4개면 7개이다
• 즉 날짜 n에 연속된 날짜 k를 빼준 값에 +1 해준 것 만큼 갯수가 나온다
• 이걸 이용하면 n-k 와 같을 때 까지 반복을 하면 된다
• 이때 이중 for문으로 j = i부터 연속된 날짜 k+1보다 작을 때 까지 반복해서 값을 더해준다
• 두번째 for문이 끝나고 변수 Max 와 더한 결과 값을 비교해 더 큰 값을 Max에 저장해주면 된다

강의 문제 풀이

---

• 구간합을 이용해 품
• 최댓값을 구하라는 문제는 최솟값부터 최대 값을 구하면 된다

#include <iostream>
#include <vector>

using namespace std;

int n, k;
vector<int> v;
int Max = -200000;
int main()
{
    int temp{};
    cin >> n >> k;
    v.resize(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        cin >> temp;
        v[i] = v[i - 1] + temp;
    }

    for (int i = k; i <= n; i++)
    {
        Max = max(Max, v[i] - v[i - k]);
    }

    cout << Max << endl;
}

• temp에 입력되는 값들을 이용해 vector에 구간합으로 저장해 준다
• for문을 k부터 n과 같을 때 까지 돌면서 큰 값을 찾아줄 것이다
• 이때 현재 vector에 i번째 저장된 값과 i-k에 저장된 값을 뺀 값이 구간합으로 구한 값에 k개만 더한 값을 구할 수 있게 되는 것이다

• 이게 무슨 소리냐 하면 사진을 보면 구간합을 1번 index부터 저장하여준뒤 두 번째 for문 연산을 하면 마지막 줄의 값이 나오게 되는 것이다
• 이렇게 구하면 더 쉽고 간결하게 구할 수 있다