# 15961. 회전 초밥

관련 알고리즘 : 투 포인터, 슬라이딩 윈도우

 

문제 링크 : https://www.acmicpc.net/problem/15961

15961번: 회전 초밥

---

문제 풀이

 

문제의 길이가 길기 때문에 조건들을 정리해보면, 

• 원래의 회전 초밥 계산법과 달리, 벨트의 임의의 한 위치부터 k개의 접시 연속해서 먹기 => 할인된 정액 가격 제공
• 초밥 종류 하나가 쓰인 쿠폰 발행, 상기 연속해서 먹기 이벤트 진행 시 => 해당 초밥 하나 추가로 무료제공. 
  • 해당 초밥이 컨베이어 벨트에 있을 때 : 그냥 먹기
  • 해당 초밥이 컨베이어 벨트에 없을 때 : 요리사가 새로 만들어 제공

<변수 조건>

• 컨베이어 벨트에 놓인 접시 수 N
• 초밥의 가짓수 d
• 연속해서 먹는 접시 수 k
• 쿠폰 번호 c

다음의 조건들로 가능한 다양한 초밥을 먹도록 하는 것이 문제의 핵심이다.

주어진 예시를 보면, k=4(k: 연속해서 먹을 수 있는 초밥의 개수), 쿠폰 번호 : 30번 초밥일 때,

좌측 상단의 9번 초밥부터 시작하면

• (9, 7, 30, 2)
• (7, 30, 2, 7)
• (30, 2, 7, 9)
• (2, 7, 9, 25)
• (7, 9, 25, 7)
• (9, 25, 7, 9)

같은 종류의 초밥이 2번 이상 나오는 조합을 삭제하면 3가지 경우가 남게 되는데,

이 때 쿠폰 번호 30번이 들어있는 조합을 제외하면 (2, 7, 9, 25) 한 종류가 남게 된다.

=> 2, 7, 9, 25, 30(무료) 총 5가지 초밥을 먹을 수 있게 되는 것이다.

 

위 예시를 통해 풀이의 흐름을 생각해 보면,

최적의 해를 갖는 특정 구간을 찾아내는 것이 관건이므로 투포인터 + 슬라이딩 윈도우 알고리즘을 사용

---

C++ 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> var; // 초밥 종류 벡터
int dish[3001]; // 연속해서 먹는 초밥 담는 배열

int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	cout.tie(NULL);

	int n; // 접시 수
	int d; // 초밥 종류
	int k; // 연속으로 먹을 수 있는 초밥 수
	int c; // 쿠폰 번호
	int sushi; // 초밥 번호
	int res = 0; 

	cin >> n >> d >> k >> c;

	dish[c] = 1; // 쿠폰 번호 초밥 미리 표시
	int cnt = 1; / 초밥 종류 표시 
	int l = 0, r = k - 1; // 투 포인터 저장

	for (int i = 0; i < n; i++) {

		cin >> sushi;
		var.push_back(sushi); // 컨베이어 벨트 위 스시 전부 var벡터에 넣기

		if (i < k) { // 연속된 k개의 초밥 넣기
			dish[sushi]++;
			if (dish[sushi] == 1) cnt++; // 개수 카운트
		}
	}
	for (int i = 0; i < k; i++)
		var.push_back(var[i]); // 컨베이어 벨트는 원형이므로, 마지막 순서에서 연속된 k개 검사

	while (1) {

		res = max(res, cnt);

		if (l == n) break; // 벨트 한바퀴 다 돌면서 확인했을 시 종료
        
		dish[var[l]]--;  // 빠지는 초밥과 새로 들어오는 초밥에 대해 cnt 개수세기
		if (dish[var[l++]] == 0) 
        	cnt--;
		dish[var[++r]]++;
		if (dish[var[r]] == 1) 
        	cnt++;
	}

	cout << res;
	return 0;
}