[15961] 회전 초밥

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

15961번: 회전 초밥

<문제>

KOI 고등부2번 문제라고한다.

직접적으로 알고리즘을 묻는 문제는 아니지만, 연관성 있는 알고리즘을 알고 있어야 떠올리기 쉽긴 하다.

 원형 슬라이딩윈도우나 투포인터처럼 구현해주면 되겠다.

 

1번부터 n번까지의 원형 인덱스를 찾기 위해서, 아래 식으로 1~n의 값을 갖는 다음 인덱스를 구할 수 있다.

idx = (idx + 1) % n + 1

 

이후, 윈도우의 한쪽에 있는 초밥을 포함하고, 반대쪽에 있는 초밥을 제거하는 방식으로 구현하면 된다.

주의할점은 양 끝에서의 '포함'과 '배제'를 정확하게 표현하기 위해서 bool이 아닌 int형으로 check배열을 생성하고,

check배열에는 해당 초밥이 윈도우에 포함된 횟수를 저장해주었다.

또한, 상수시간만에 score를 계산하기 전에 윈도우 내의 초밥의 종류를 cnt라는 변수에 저장해주고

최종 score를 계산하기 전에 쿠폰초밥에 대한 처리만 해주면 된다.

쿠폰초밥이 한번도 포함되지 않았다면, 최종 score는 +1해주면 되고 그 외에는 score를 유지해준다. 

 

<소스코드>

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int n, d, k, c, cnt, ans;
int a[3000003];
int check[3003];
int main(void) {
    int i;
    scanf("%d %d %d %d", &n, &d, &k, &c);
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        if (i < k && check[a[i]] >= 1)
            check[a[i]]++;
        else if (i < k && check[a[i]] == 0) {
            check[a[i]] = 1;
            cnt++;
        }
    }
    if (check[c] == false) {
        ans = cnt + 1;
    }
    else ans = cnt;
    int next = 0, pre = 0;
    for (i = 0; i < n; i++) {
        next = (k + i) % n;
        pre = i % n;
        if (check[a[next]] >= 1)
            check[a[next]]++;
        else if (check[a[next]] == 0) {
            check[a[next]] = 1;
            cnt++;
        }
 
        if (check[a[pre]] == 1) {
            check[a[pre]] = 0;
            cnt--;
        }
        else if (check[a[pre]] >= 2) {
            check[a[pre]]--;
        }
        if (check[c] == 0) {
            ans = max(cnt + 1, ans);
        }
        else ans = max(cnt, ans);
    }
    printf("%d", ans);
    return 0;
}