[백준/C++] 2531번: 회전 초밥

 

접근 방법

a 배열을 통해 초밥의 가짓수 d(2 ~ 3000)가 k개의 접시를 연속해서 먹을 때 있는지 확인
먼저 반복문을 돌려서 0 ~ k-1 접시를 연속으로 먹었을 때 최댓값을 계산(윈도우로 활용)
해당 윈도우를 접시를 지우고, 추가하며 연속된 접시를 k 개 먹었을 때, 최댓값을 계산(슬라이딩 윈도우)

 

코드

#include <iostream>
#include <vector>

using namespace std;

int a[3001] = {0, };

int main() {
    int N, d, k, c;
    cin >> N >> d >> k >> c;

    vector<int> v(N);
    for (int i = 0; i < N; i++) cin >> v[i];

    int sol = 0, result = 0;


    for (int i = 0; i < k; i++) {
        if (a[v[i]] == 0) result++;
        a[v[i]]++;
    }

    sol = result + (a[c] == 0 ? 1 : 0);

    for (int i = 1; i < N; i++) {
        int removeIdx = v[(i-1)%N];
        a[removeIdx]--;
        if (a[removeIdx] == 0) result--;

        int addIdx = v[(i+k-1)%N];
        if (a[addIdx] == 0) result++;
        a[addIdx]++;

        sol = max(sol, result + (a[c] == 0 ? 1 : 0));
    }

    cout << sol;

    return 0;
}