문제 출처

1. 문제설명

  • 초밥의 번호가 주어진다.
  • 임의의 한 위치부터 k개의 접시를 연속해서 먹는다.
  • 만약, 먹은 초밥들의 인접한 위치에 쿠폰번호가 있으면, k+1개를 먹을 수 있다.
    • 단, 인접한 위치에 쿠폰 번호의 초밥이 있어야 한다.



2. 알고리즘 설계

  • 이 문제는 슬라이딩 윈도우 문제이다.
    • 초밥은 원형이므로, k가 2라면 0, n-1번째도 인접하므로 해당된다.
  • 0번부터 4개씩 마지막 index까지 구현은 매우 쉽다.
  • 그러면 위에 언급한 0번째와 n-1번째가 포함되어 있다면 어떻게 해야할까?
    • 바로 나머지 연산이다.
    • 현재 위치의 index를 n개로 나눈 나머지를 index로 취하면 된다!



3. 로직

  • 0~N-1번째의 초밥이 입력되었다.

  • k=4일 때, 슬라이딩 윈도우 알고리즘은 다음과 같다.

     	for (int i = 0; i < n; i++) {
      for (int j = i; j < i + 4; j++) {
          int cur = v[j % n];
      }
  • 이제 매 순간 4개씩 방문해주면서,
  • 방문한 index를 체크한다.
    • 마지막 순간에 쿠폰을 방문하지 않았다면,
    • 정답에 1을 추가해주면 된다.



4. 전체 코드

#include <bits/stdc++.h>
using namespace std;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n, d, k, c, ans = 0;
	cin >> n >> d >> k >> c;

	vector<int> v(n);
	vector<bool> chk;

	for (int i = 0; i < n; i++)
		cin >> v[i];

	for (int i = 0; i < n; i++) {
		int cmp = 0;
		chk.assign(d + 1, false);

		for (int j = i; j < i + k; j++) {
			int cur = v[j % n];

			if (!chk[cur]) {
				cmp++;
				chk[cur] = true;
			}
		}
		if (!chk[c]) cmp++;
		ans = max(ans, cmp);
	}

	cout << ans;
	return 0;
}