급하게임개발

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

처음에 이문제는 dp로 접근했다가 시간초과를 맞고 다시 생각해보았다

나는 처음0번부터 k-1번 인덱스 까지의 초밥의 종류를 저장해 놓고 슬라이딩 윈도우에서 해당 인덱스가 나가거나 들어올 때 isEat배열의 요소를 비교해서 인덱스가 빠질때 isEat이 0이될때는 해당 초밥을 안먹는거니 종류에서 빼주고 들어올 때 1이면 이제 먹는 거니 종류에서 +1해줬다

#include <iostream>
#include <vector>
using namespace std;
vector<int> inputData;
int isEat[3001] = { 0, };
int n, d, k, c;
int GetEat() {
	int total=0;
	for (int i = 0; i <= d+1; i++) {
		if (isEat[i] > 0) {
			total += 1;
		}
	}
	return total;
}
int main() {
	iostream::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> d >> k >> c;
	inputData.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> inputData[i];
	}
	int ans=0;	

	for (int i = 0; i < k; i++) {
		isEat[inputData[i]] += 1;
	}
	isEat[c] += 1;
	ans = GetEat();
	int maxAns = ans;
	for (int i = 1; i < n; i++) {
		isEat[inputData[i - 1]] -= 1;
		if (isEat[inputData[i - 1]] == 0) {
			ans -= 1;
		}
		isEat[inputData[(i + k-1)%n]]+=1;
		if (isEat[inputData[(i + k - 1) % n]] == 1) {
			ans += 1;
		}
		
		maxAns = max(ans, maxAns);
	}
	cout << maxAns;
}