[백준 : 21921] 블로그 [C/C++] (슬라이딩 윈도우)

 

블로그에 블로그라는 이름의 문제 풀이 적기

푸하하하핫!! 으하하핫!!

사실 하나도 안 웃기다. 공부하기 싫어..

 

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

이 문제는 한창 투포인터/슬라이딩윈도우 공부하던 시절의 문제다. ez

    ㄴ 사실 너무 힘들었어요

사실 이 정도로 명쾌한 문제면 투포인터/슬라이딩윈도우 개념이 없어도 머리만 좋으면 풀 수 있을듯 하다.

 

X일이라고 구간의 넓이를 줬다. 아~ 냅다 슬라이딩 윈도우를 사용하면 된다는 것을 감으로 알 수 있다.

안오면 앞으로 돌아가서 뇌에 힘주는 훈련부터 하고 오길 바란다.

 

사실 초보들은 언제나 그랫듯 반복문 사용하면 되는거 아냐?라고 생각 할 수 있을텐데, 해보면 안다. 안됨

X와 N의 범위가 크기 때문이다. 이 문제를 반복문으로 풀려면 중첩 반복문의 은혜가 끝이 없을테니, 안된다.

 

슬라이딩 윈도우 사용해야겠지?

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int N, X;

int pref_sum[250001];

int main(void){

    cin >> N >> X;

    int i;
    for(i = 1; i<=N; i++){ // 누적 합 배열 만들기
        int t;
        cin >> t;
        pref_sum[i] = pref_sum[i-1] + t; 
    }

    int ptr = 1;
    int cntP = 0;
    int maxP = -1;


    while(ptr+X<=N+1){
        int w = pref_sum[ptr+X-1] - pref_sum[ptr-1]; // 이 부분에서 내가 원하는 구간이 구해지는지를 직접 써보는 게 좋을 것 같다. 머리로만 생각하면 틀리기 쉽상
        if(w>maxP){
            cntP = 1;
            maxP = w;
        }
        else if(maxP!=0 && w==maxP) cntP++;
        ptr++;
    }

    if(maxP==0){
        cout << "SAD";
        return 0;
    }

    cout << maxP << "\n" << cntP << "\n";

}

 

구간합 배열 구간이 살짝 헷갈려서 시행착오가 있었다. cnt도 뭔가 원치 않게 꼬이는 경우가 있어서, 그 값도 제대로 찾는 것이 중요한 듯 하다. 언제나 그렇듯, 가장 중요한 관건은 내 코드가 제대로 돌아가고 있는게 맞는지 디버깅하고, 손으로도 직접 적어보는 것.