[백준] 회전 초밥 2531번 (c++)

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

 

풀이 방법

 

완전 탐색으로 풀이했다.

완전 탐색으로 풀이하려면 원형 배열이기 때문에 끝에 가서 인덱스의 처리하기가 애매해질 수 있기 때문에, 배열 길이를 n+k로 설정하고, 뒤에 남은 것을 추가해 주었다.

 

시뮬레이션을 진행할 때, 다음 음식이 새로운 음식인지 판별하기 위해 visited배열을 두어 선택한 k개에 있는 음식인지 판별했다.

다음 것을 선택하고 visited배열을 초기화하고, 제일 처음 선택한 것을 제거해 주는 방법으로 시뮬레이션을 진행했다.

 

// ConsoleApplication3.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

#include <iostream>
#include <algorithm>

using namespace std;

int n, d, k, c; // 접시의 수, 초밥의 가짓수, 연속해서 먹는 접시의 수, 쿠폰 번호 c

int dish[33001];
// visited를 두고, 만약 존재한다면 k--, 없으면 ++
int visited[3001];
int kind = 0; // 음식의 종류
int num = 0, ans = 0;
// 회전 초밥을 완탐하며 다른 것의 개수를 구하기
// 
int main() {
	cin >> n >> d >> k >> c;
	int temp;
	for (int i = 0; i < n; i++) {
		cin >> dish[i];
	}
	for (int i = 0; i < k; i++) {
		dish[n + i] = dish[i];
	}

	for (int i = 0; i < n + k; i++) {						
		int temp = dish[i]; // 다음 음식 추가
		visited[temp]++; 
		if (visited[temp] == 1) { // 처음 방문한 경우 (기존에 존재하지 않은 경우)
			kind++;
			if (ans <= kind) {
				if (visited[c] == 0) ans = kind + 1;
				else ans = kind;
			}
		}
		if (num < k) num++; // 초기 k개를 선택하지 않은 경우
		if (num == k) {  // 초기 k개가 선택된 경우
			int before = dish[i - k + 1]; // 가장 초반에 선택한 음식
			visited[before]--;
			if (visited[before] == 0) kind--; // 0개라면 카운트 제거
		}
	}
	cout << ans;
	return 0;
}