[백준] 21921번: 블로그

문제

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

소요 시간

• 문제 이해 : 15분
• 풀이 : 20분

접근 방법

1) 완전탐색
1. 배열을 돌면서
2. X기간별 다 더해보고
3. max 값을 갱신하며 개수를 센다.

2) 슬라이딩 윈도우
2중 반복문을 없애기 위해, 0~X까지 초기합을 구한다음 앞으로 한 칸씩 이동하였다.

풀이

1차 시도

#include <iostream>
#include <vector>

#define MAX 250000
using namespace std;

int N, X;
int visitCnt[MAX+4];
int maxVisit;

int main() {

    cin >> N >> X;

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


    // 배열을 돈다
    int maxSum = 0;
    int cnt = 0;

    for(int i=0; i<=N-X; i++) {
        // i = 1 ~ N-X
        // j = i ~ i+X 까지 더하기 

        int sum = 0; 
        for(int j=i; j<i+X; j++) {
            sum += visitCnt[j];
        }
        
        // max보다 크면 
        if (maxSum < sum) {
            maxSum = sum;  
            cnt = 1;
        } else if (maxSum == sum) {  // max와 같으면 
            cnt++;
        }
    }

    if (maxSum == 0) {
        cout << "SAD";
    } else {
        cout << maxSum << '\n' << cnt << '\n';
    }

    return 0;
}

결과 : 시간초과

2중 반복문인데 X가 250,000이기 때문에 시간 초과가 날 수 있었을 것 같다.

2차 시도

#include <iostream>
#include <vector>

#define MAX 250000
using namespace std;

int N, X;
int visitCnt[MAX+4];
int maxVisit;

int main() {

    cin >> N >> X;

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


    int sum = 0; 

    int startIdx = 0;
    int endIdx = startIdx + X;
    // 0 ~ N-X 값 더해주기 
    for(int i=startIdx; i<endIdx; i++) {
        sum += visitCnt[i];
    }

    // 초기화
    int maxSum = sum;
    int cnt = 1;

    // 앞으로 이동하면서, sum - 맨앞요소 && sum + 그 다음요소 해주기 
     for(endIdx; endIdx<N; endIdx++) {
        sum -= visitCnt[startIdx]; 
        sum += visitCnt[endIdx];
        

        startIdx++;

        // max보다 크면 
        if (maxSum < sum) {
            maxSum = sum;  
            cnt = 1;
        } else if (maxSum == sum) {  // max와 같으면 
            cnt++;
        }
    }

    if (maxSum == 0) {
        cout << "SAD";
    } else {
        cout << maxSum << '\n' << cnt << '\n';
    }

    return 0;
}

결과 : 통과

정리

시간 초과 날 수 있는 부분을 다시 한번 체크하자