[백준] 회전초밥

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

2531번: 회전 초밥

우선 문제부터 간단하게 요약하면, 

회전 초밥 벨트에 초밥들이 놓여 있는데, 연속한 k개와 쿠폰의 초밥을 먹을 때, 초밥 종류가 가장 많아지게 먹는다면, 총 몇개의 초밥을 먹을 수 있는지를 구해야 하는 문제입니다.

 

<Solution>

이 문제의 경우, 접시의 수가 30,000개로 엄청 크지 않으므로, 

1칸씩 window를 이동하며, 내부의 초밥 종류를 새로 계산하는 방식으로 해결이 가능합니다.

 

check array를 두어 index가 초밥번호가 되도록 하면, checking이 가능합니다.

 

실제 구현은 아래와 같습니다.

#include <iostream>
#include <cstring>
using namespace std;

int N, D, K, C;
int A[3000000+10];
int check[3000+10];
void InputData(){
    cin >> N >> D >> K >> C;
    for (int i=0; i<N ; i++){
        cin >> A[i];
    }
}

int solve(){
    int ans = 0;
    for(int i = 0; i<N; i++){
        if(ans == K+1) return ans;
        memset(check, 0, sizeof(check));
        int num_sushi = 0;
        for(int j = 0; j<K; j++){
            if (!check[A[(i+j)%N]]){
                check[A[(i+j)%N]] += 1;
                num_sushi ++;
            }
        }
        if(!check[C]) num_sushi++;

        ans = max(ans, num_sushi);


    }
    return ans;
}


int main(){
    int ans = -1;

    InputData();// 입력받는 부분

    // 여기서부터 작성
    ans = solve();
    cout << ans << endl;// 출력하는 부분
    return 0;
}