2559 : 수열 - 구간합, 슬라이딩 윈도우

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

2559번: 수열

 

문제 요약

n개 범위의 구간 합 중 최대값을 출력

 

난이도

Silver 3

---

풀이

• 구간합(prefix sum)
• 최댓값 갱신
• 슬라이딩 윈도우

---

REVIEW

 

단순하게 중첩 for문으로 시작점으로부터 N개의 원소를 더해 vector에 push_back()했더니 메모리 초과.

vector형이 문제인가 싶어 int 배열로 바꾸었더니 시간 초과가 났다.

 

정답률이 35%인데 너무 단순하게 접근한 것부터 의심했어야 했다.

 

누적합 문제구나. 싶어 풀이를 바꾸어 풀었더니 인덱스가 헷갈려 여러 번의 오답 끝에 맞췄다.

인덱스가 헷갈릴 땐 테스트 케이스로 손으로 적어 풀기.

암산으로 하려니 계속 틀린다.

슬라이딩 윈도우 연습하기에도 좋은 문항이라고 하니, 다른 풀이도 익혀둬야겠다.

---

CODE

• 구간합
• 최댓값 갱신 : max 이용해 최댓값을 갱신하는 형식

#include <bits/stdc++.h>
using namespace std;

int n,k,temp,psum[100001],ret = -100000004; // 넉넉하게 설정

int main(){
    cin >> n >> k;

    for(int i = 1; i <= n; i++){
        cin>> temp;
        psum[i] = psum[i-1] +temp; 
    }

    for(int i = k; i <=n; i++){
        ret = max(ret,psum[i] - [sum[i-k]]);// 최댓값은 최소를 정해두고 갱신하는 형식으로 구한다는 것
                                            // 나는 다 넣고 정렬 후 마지막 원소 뽑음
    }

    cout << ret <<'\n';
    return 0;
}

• 슬라이딩 윈도우 : 0~K까지의 구간합을 구하고, 그 다음 요소 추가하고, 가장 첫 요소 빼고 하는 식으로 밀면서 구현.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, K;
    cin >> N >> K;
    int A[N];
    for (int i = 0; i < N; i++)
        cin >> A[i];

    // 윈도우(구간)의 크기는 K
    int answer, result = 0;
    for (int i = 0; i < K; i++)
        result += A[i]; // [0, K - 1] 구간
        
    answer = result;

    for (int i = K; i < N; i++)
    { // [i - K + 1, i] 구간
        result += A[i];
        result -= A[i - K];
        answer = max(answer, result);
    }

    cout << answer;
}