백준2531 회전 초밥

작성일 | In

문제 링크

  • http://icpc.me/2531

문제 출처

  • 2012 지역 본선 중등2

사용 알고리즘

  • Sliding Window

시간복잡도

  • O(n)

풀이

arr[i]는 i번째 초밥의 종류가 숫자로 저장되어 있고, cnt[i]에는 탐색 도중 종류의 번호가 i인 초밥을 몇 개 먹었는지를, now변수에는 현재 초밥을 몇 가지 먹었는지를 저장합니다.
goRight(int a)함수는 a를 먹는다는 의미이고, goLeft(int a)함수는 a를 먹지 않는다는 의미입니다. 조금 더 자세히 설명하자면, goRight(int a)는 현재 리스트에 a를 추가하고 goLeft(int a)는 현재 리스트에서 a를 제거하는 의미입니다.

먼저, arr배열에 데이터를 입력 받습니다. 단, 환형으로 구성되어야 하기 때문에 입력받은 데이터를 뒤에 그대로 붙여주도록 합니다.
쿠폰으로 먹을 수 있는 초밥은 무조건 먹는것이 좋습니다. 그러므로 쿠폰으로 먹을 수 있는 초밥을 먹도록 합시다.
그 후, 일단 0번부터 k-2번까지 총 k-1개의 초밥을 먹어봅시다.

이제 i가 0부터 n-1까지 돌면서 i+k-1번째 초밥을 먹고, i번째 초밥을 뱉을겁니다.
초밥을 먹게 되면 연속된 k개의 초밥을 먹게 되는 것이고, 초밥을 뱉게 되면 다시 연속된 k-1개의 초밥을 먹은 상태로 돌아가게 됩니다.
for문을 돌때마다 max값을 갱신해주면 답을 구할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;

int n, d, k, c;
int arr[60010]; //초밥 상태
int cnt[3010]; //내가 먹은거!
int now; //현재 먹은 종류

void goRight(int a){
	if(!cnt[a]) now++; //안먹은거면 먹을거
	cnt[a]++; //먹은거 추가
}

void goLeft(int a){
	cnt[a]--; //먹은거 뱉음
	if(!cnt[a]) now--; //다 뱉었으면 삭제
}

int main(){
	int ans = 0;
	cin >> n >> d >> k >> c;
	for(int i=0; i<n; i++) scanf("%d", arr+i);
	for(int i=0; i<k-1; i++) arr[n+i] = arr[i];
	goRight(c);
	for(int i=0; i<k-1; i++){
		goRight(arr[i]);
	}
	for(int i=0; i<n; i++){
		goRight(arr[i+k-1]);
		ans = max(ans, now);
		goLeft(arr[i]);
	}
	printf("%d", ans);
}