(백준/C++) 2531 회전초밥

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

문제 해석(시간 제한 1초)

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

사실상 1번 조건은 필요없는 조건이라 보시면 될 것 같습니다. 왜냐하면, 해당 문제에서 가격과 관계하여 계산을 필요로 하는 것이 없기 때문입니다.

그러므로, 연속으로 먹는 것이라는 키워드에 집중해서 문제를 푸시면 될 것 같습니다. 이 문제의 핵심은 '연속으로 먹으면서 최대한 겹치지 않는 경우의 수를 찾는 것(+쿠폰)'이라고 생각합니다. 연속으로 먹는 것은 투 포인터 알고리즘을 이용해주면 될 것 같습니다.

처음에는 start와 end를 설정한 투포인터를 구성해 문제를 풀어나갔는데 갈수록 초밥의 중복제거에 대한 문제가 발생했습니다. 단순히, bool check[]를 이용해서 하게되면 어느 것이 먼저 들어오고 나가야하는지 start와 end를 통한 투포인터 알고리즘은 문제를 해결하기 어려웠습니다...

결국에는 다른 것으로 풀어보기로 했습니다. 바로, 슬라이딩 윈도우를 이용해서 풀면 쉽게 풀릴 것 같다는 생각이 들었습니다. 시간 자체는 위에 언급된 것보다 많이 걸릴테지만, 최대 시간 복잡도는 O(30000 * 3000)정도 밖에 안걸리기 때문에 문제 없이 해결할 수 있습니다.

만약 중복일 경우 flag++를 통해 중복의 개수를 파악하는 것입니다. 그런후 계산할때 k-flag+coupon을 통해 답을 도출해 나가는 것입니다.

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n, d, k, c; // 접시의 수, 초밥의 가짓수, 연속해서 먹는 접시의 수, 쿠폰 번호
int arr[30001]; // 회전 초밥 테이블
bool check[30001];
int maxCnt = 0;

int main() {
    cin >> n >> d >> k >> c;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    for(int i = 0; i < n; i++) {
        int flag = 0;
        int coupon = 1;
        for(int j = i; j < i + k; j++) {
            if(!check[arr[j % n]]) check[arr[j % n]] = true;
            else flag++;
        }
        if(check[c]) coupon = 0;
        maxCnt = max(maxCnt, k - flag + coupon);
        memset(check, false, sizeof(check));
    }
    cout << maxCnt << endl;
    return 0;
}