Boj 2531 c++ 회전초밥

 

 

첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ k ≤ 3,000 (k ≤ N), 1 ≤ c ≤ d이다. 두 번째 줄부터 N개의 줄에는 벨트의 한 위치부터 시작하여 회전 방향을 따라갈 때 초밥의 종류를 나타내는 1 이상 d 이하의 정수가 각 줄마다 하나씩 주어진다.

 

이때 쿠폰을 사용하고, 연속해서 먹을 수 있는 초밥을 선태하여 먹을 수 있는 초밥의 종류의 최댓값을 구하는 것이 문제이다.

n, d, k, c입력 받는다.
n:초밥의 개수
d:종류
k:연속해서 먹을 수 있는 접시 수 
c:쿠폰의 번호

n개의 초밥의 종류가 입력으로 주어진다.

n번 만큼 반복문을 돌려 d이하의 회전초밥의 종류를 입력받는다.

이때, 회전초밥이므로 원형 배열을 구현해야하기 때문에 
배열의 크기를 2n+1만큼으로 잡고, 같은 입력값을 배열 끝에 붙인다.



이때, 두 포인터를 이용하여 k개 만큼의 접시를 먹는 경우의 수를 모두 구해준다.

초기값 head는 0이며,  tail=k-1이다.

인덱스가 d+1까지 존재하는 벡터의 초기값을 0으로 저장해놓은 다음

한번 반복할 때 마다 head++; tail++을 해준 후, 그 부분에서 존재하는 수의 인덱스를 가진 부분의 값을 1로 바꾸어준다.

쿠폰의 인텍스를 가진 부분도 1로 바꾸어준다.

전체 벡터에서 모두 실행을 해본 뒤, 1의 값을 가진 인덱스의 개수의 최댓값을 구하여 출력한다.

두포인터 알고리즘을 사용할 때 불필요한 반복작업을 하지 않도록 범위를 올바르게 정하는 것이 중요하다.

 

 

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

int main(){

    int n, d, k, c;

    cin>>n>>d>>k>>c;

    vector<int> sushi(2*n+1, 0);
    vector<int> v(d+1);

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

    int head=0, tail=k-1;
    int Max=0;


    while(head<n){
        int cnt=0;
        for(int i=0; i<=d; i++){
            v[i]=0;}
        v[c]=1;

        for(int i=head; i<=tail; i++){
            v[sushi[i]]=1;
        }
        for(int i=0; i<=d; i++){
            if(v[i]==1)
                cnt++;


        }
        if(Max < cnt) {
                Max=cnt;
            }
       ++head;
       ++tail;

    }

    cout<<Max;

}