[BAEKJOON] 2531번 회전초밥

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

2531번: 회전 초밥

문제조건

1.  k개의 접시 연속해서 먹으면 정액할인 가격
2. 1번에 해당할때, 초밥 번호 쿠폰발행, 그 번호 공짜, 번호 없으면 새로 만들어줌
3. 손님이 먹을 수있는 초밥종류의 최댓값?

가장 많이 먹을 수 있는 경우? 쿠폰발행된 것이 아닌 초밥들을 연속해서 먹는다.

 

뭔가 투포인터를 이용해서 풀어야만 할 것같았는데, 투포인터를 활용한  '슬라이딩 윈도우' 기법을 활용했다.

거창해 보이지만 단순하게 말하면 창문을 밀고 당길때, 창문의 길이는 계속 일정한 것과 같이, 탐색하고자하는 길이는 고정 시키고, 전체 배열을 탐색할 수 있는 기법이다.

 

원형으로 찾아야하므로, n으로 나눈 나머지로 구해줬고, k개를 연속으로 먹는 경우이므로 k개를 슬라이딩 윈도우로 탐색해줬다. 또한 처음부터 쿠폰이있다고 가정해서 coupon = 1로 두고, 만약 k개안에 쿠폰이 나온다면 coupon = 0 으로 변경했다.

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

// 1. k개의 접시 연속해서 먹으면 정액할인 가격
// 2. 1번에 해당할때, 초밥 번호 쿠폰발행, 그 번호 공짜, 번호 없으면 새로 만들어줌

vector<int> v;
int n, d, k, c, visited[3001];

int main() {
	cin >> n >> d >> k >> c;
	for (int i = 0; i < n; i++) {
		int rice;
		cin >> rice;
		v.push_back(rice);
	}
	int flag = 0, coupon = 0, res = 0;
	//슬라이딩 윈도우
	for (int i = 0; i < n; i++) {
		flag = 0;
		coupon = 1;
		for (int j = i; j < i + k; j++) {
			//이미 있던 초밥(중복)
			if (visited[v[j % n]] == 1) flag++;
			//처음 등장한 초밥
			else visited[v[j % n]] = 1;
			//쿠폰일경우
			if (v[j % n] == c) coupon = 0;
		}
		res = max(res, k - flag + coupon);
		memset(visited, 0, sizeof(visited));
	}
	cout << res;
}

굿,,!