BOJ 2531 - 회전 초밥

2531번: 회전 초밥 (acmicpc.net)

 

접근 방법

초밥을 연속 K를 먹었을 때, 먹을 수 있는 가장 많은 가짓 수를 선택하는 문제이다.

이 문제에서 주의 깊게 봐야할 것이 쿠폰이다.

 

처음에 쿠폰이 해당 쿠폰의 초밥을 먹을 때, 추가로 1개를 더 먹는 거라고 착각했다.

그러나 이 문제에서 " 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다." 를 고려하지 않은 문제풀이이다.

 

따라서, 해당 쿠폰의 초밥을 안 먹은 경우 가지 수를 1가지 추가하고 슬라이딩 윈도우를 하면 된다.

 

코드

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

#define ll long long

using namespace std;

int n, d, k, c;
vector<int> v;

int selectChk[300001];

int main() {
	cin >> n >> d >> k >> c;
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		v.push_back(tmp);
	}
	
	int res = 0;
	int cnt = 0;
	bool flag = false;
	int idx = 0;
	int max_k = k;
	for (int i = 0; i < n; i++) {
		if (i == 0) {
			
			
			while (max_k < n - 1 && idx < max_k) {
				int target = v[idx];

				selectChk[target]++;
				if (selectChk[target] == 1) {
					cnt++;
				}

				idx++;
			}

			if (selectChk[c] == 0) {
				selectChk[c]++;
				cnt++;
			}
		
		}
		else {
			int front = v[i - 1];
			int rear = v[(i + max_k - 1) % n];

			selectChk[front]--;
			if (selectChk[front] == 0) {
				cnt--;
			}

		
			selectChk[rear]++;
			if (selectChk[rear] == 1) {
				cnt++;
			}

			
			if (selectChk[c] == 0) {
				selectChk[c]++;
				cnt++;
			}

			
		}
		res = max(res, cnt);
	}
	cout << res;
}