백준 15961 - 회전 초밥

문제 설명

회전 초밥 음식점에는 회전하는 벨트 위에 여러 가지 종류의 초밥이 접시에 담겨 놓여 있고, 손님은 이 중에서 자기가 좋아하는 초밥을 골라서 먹는다. 초밥의 종류를 번호로 표현할 때, 다음 그림은 회전 초밥 음식점의 벨트 상태의 예를 보여주고 있다. 벨트 위에는 같은 종류의 초밥이 둘 이상 있을 수 있다. 

새로 문을 연 회전 초밥 음식점이 불경기로 영업이 어려워서, 다음과 같이 두 가지 행사를 통해서 매상을 올리고자 한다.

1. 원래 회전 초밥은 손님이 마음대로 초밥을  고르고, 먹은 초밥만큼 식대를 계산하지만, 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공한다. 
2. 각 고객에게 초밥의 종류 하나가 쓰인 쿠폰을 발행하고, 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종류의 초밥 하나를 추가로 무료로 제공한다. 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다.  

위 할인 행사에 참여하여 가능한 한 다양한 종류의 초밥을 먹으려고 한다. 위 그림의 예를 가지고 생각해보자. k=4이고, 30번 초밥을 쿠폰으로 받았다고 가정하자. 쿠폰을 고려하지 않으면 4가지 다른 초밥을 먹을 수 있는 경우는 (9, 7, 30, 2), (30, 2, 7, 9), (2, 7, 9, 25) 세 가지 경우가 있는데, 30번 초밥을 추가로 쿠폰으로 먹을 수 있으므로 (2, 7, 9, 25)를 고르면 5가지 종류의 초밥을 먹을 수 있다. 

회전 초밥 음식점의 벨트 상태, 메뉴에 있는 초밥의 가짓수, 연속해서 먹는 접시의 개수, 쿠폰 번호가 주어졌을 때, 손님이 먹을 수 있는 초밥 가짓수의 최댓값을 구하는 프로그램을 작성하시오. 

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N개의 초밥을 K개씩 연달아 먹을 때, 가장 많은 가짓수를 먹는 경우를 골라야 한다.

이때, C에 해당하는 초밥은 추가로 먹을 수 있는 점을 고려해야 한다.

 

N이 3,000,000이기 때문에 모든 초밥을 4개씩 확인하는 것은 시간초과가 걸릴 것이다.

따라서, 슬라이딩 윈도우를 이용하면 된다.

처음 초밥을 기준으로 k개의 초밥을 벡터에 넣어놓고 그 안에 있는 초밥의 가짓수를 세면 된다.

이후, 오른쪽으로 한칸씩 이동하며 초밥의 가짓수를 제어하면 된다.

제일 앞에 있는 초밥은 오른쪽으로 이동하면 제외될 것이다.

따라서, 그에 해당하는 가짓수를 1 빼준다.

반대로 오른쪽에 있는 초밥은 이번에 추가된 초밥이기 때문에 가짓수를 1 늘린다.

이 과정을 진행한 후, 정답을 갱신하면 된다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int N, d, k, c;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(4);  

    cin >> N >> d >> k >> c;

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

    vector<int> check(d+1, 0);
    deque<int> current;

    check[c] = 1;
    int ans = 1;
    int cnt = 1;

    for (int i = 0; i < k; i++)
    {
        int sushi = sushies[i];
        current.push_back(sushi);
        check[sushi]++;
        if (check[sushi] == 1) cnt++;
    }

    ans = max(ans, cnt);

    for (int i = k; i < N + k; i++)
    {
        int front = current.front();
        current.pop_front();
        check[front]--;
        if (check[front] == 0) cnt--;

        int sushi = sushies[i % N];
        current.push_back(sushi);
        check[sushi]++;
        if (check[sushi] == 1) cnt++;

        ans = max(ans, cnt);
    }

    cout << ans;

    return 0;
}

---