[백준 15961] 회전 초밥

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

15961번: 회전 초밥

#include <cstdio>
int N, d, k, c;	// 접시수, 가짓수, 연속, 쿠폰번호
int lookup[3000 + 2];
int plate[3000000 + 2];

void input()
{
	scanf("%d %d %d %d", &N, &d, &k, &c);
	for (int i = 0; i < N; i++) {
		scanf("%d", &plate[i]);
	}
}


int get_max()
{
	int max = 0;	// 최대가짓수
	int cnt = 1;	// 현재 먹은 가짓수	// 쿠폰의 초밥은 무조건 먹는다. 
	lookup[c] = 1;	

	// 초기 룩업테이블 생성 
	for (int i = 0; i < k; i++) {
		lookup[plate[i]] += 1;
		if (lookup[plate[i]] == 1) cnt++;	// 종류 한 개가 방금 추가됨
	}

	for (int i = 1; i < N; i++) {
		lookup[plate[(i + k - 1) % N]] += 1;
		if (lookup[plate[(i + k - 1) % N]] == 1) cnt++;

		lookup[plate[i - 1]] -= 1;
		if (lookup[plate[i - 1]] == 0) cnt--;

		max = (max < cnt) ? cnt : max;
	}
	return max;
}



int main()
{
	input();
	int ans = get_max();
	printf("%d\n", ans);
	return 0;
}

이 문제는 [백준 2531] 회전초밥 문제와 동일하게 풀면 타임아웃이 발생한다. 

이유는 인풋 배열 크기가 100배 차이 나기 때문이다.

실버 문제에서는 diff 배열에서 0이 아닌 원소를 체크하며 cnt를 세어줬다면, 이 문제에서는 "슬라이딩 윈도우"를 통해 해결해야 한다. 

 

 

// get_max() 함수

쿠폰의 초밥은 항상 먹을 수 있으므로 cnt = 1, loolup[c] = 1로 초기화한다. 

 

첫 번째 루프에서는 처음 k개를 돌면서, 초기 슬라이딩 윈도우를 만들어 준다. 

초밥을 먹고 난 후 룩업 테이블의 값이 0에서 1로 바뀌었다면, 새로운 종류의 초밥을 먹은 것이므로 cnt를 증가시킨다. 

 

두 번째 루프는 슬라이딩 윈도우를 한 칸씩 이동하며 탐색하는 용도이다. 

이미 첫번째 루프에서 인덱스  i = 0에 대하여 연속해서 k개의 초밥을 먹었을 경우를 탐색해주었기 때문에, 인덱스 i = 1부터 탐색을 진행한다. 

만약 (i + k -1) % N 번째 초밥을 먹고 난 후, 룩업테이블의 값이 0에서 1로 바뀌었다면, 새로운 종류의 초밥을 먹은 것이므로 cnt를 증가시킨다. 

한편 슬라이딩 윈도우의 크기를 항상 k로 유지해주기 위해 i - 1번째 먹었던 초밥은 삭제해준다. 제거 후 룩업테이블의 값이 1에서 0으로 바뀌었다면, 한 종류의 초밥이 삭제된 것이므로 cnt를 감소시킨다. 

 

매 탐색 후 max 값과 cnt 값을 비교하여 먹을 수 있는 가짓수의 최대값을 갱신해준다.