백준 15961 회전 초밥

작성일 | In |

Problem : 회전 초밥

유형 : 슬라이딩 윈도우

문제 설명

그림

새로 문을 연 회전 초밥 음식점이 불경기로 영업이 어려워서, 다음과 같이 두 가지 행사를 통해서 매상을 올리고자 한다.

원래 회전 초밥은 손님이 마음대로 초밥을 고르고, 먹은 초밥만큼 식대를 계산하지만, 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공한다. 각 고객에게 초밥의 종류 하나가 쓰인 쿠폰을 발행하고, 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종류의 초밥 하나를 추가로 무료로 제공한다. 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다.
위 할인 행사에 참여하여 가능한 한 다양한 종류의 초밥을 먹으려고 한다. 위 그림의 예를 가지고 생각해보자. k=4이고, 30번 초밥을 쿠폰으로 받았다고 가정하자. 쿠폰을 고려하지 않으면 4가지 다른 초밥을 먹을 수 있는 경우는 (9, 7, 30, 2), (30, 2, 7, 9), (2, 7, 9, 25) 세 가지 경우가 있는데, 30번 초밥을 추가로 쿠폰으로 먹을 수 있으므로 (2, 7, 9, 25)를 고르면 5가지 종류의 초밥을 먹을 수 있다.

회전 초밥 음식점의 벨트 상태, 메뉴에 있는 초밥의 가짓수, 연속해서 먹는 접시의 개수, 쿠폰 번호가 주어졌을 때, 손님이 먹을 수 있는 초밥 가짓수의 최댓값을 구하는 프로그램을 작성하시오.

예제 입력

1
2
3
4
5
6
7
8
9
8 30 4 30
7
9
7
30
2
7
9
25

예제 출력

1
5

해결 전략

쿠폰을 이용하는것이 항상 유리하다.
쿠폰의 초밥은 항상 먹고 시작한다.

초밥을 먹을때 이전에 먹었던 종류의 초밥인지 확인한다.
만약 처음 먹는 종류의 초밥이라면, 먹은 종류의 개수를 증가시키고 최대값과 비교해본다.

연속으로 먹을 수 있는 초밥의 개수를 초과한 경우, 가장 최근에 먹은 초밥을 뱉는다.
초밥을 뱉을때, 지금까지 해당 초밥의 개수를 재보고, 0개라면 먹은 종류의 개수를 감소시킨다.

주의할 점

  • n의 크기가 300만이지만, 충분히 메모리 제한내 해결이 가능하다.

풀이

초밥을 배치 한다.

환형 큐를 이용해도 되지만, 배열을 이용해도 충분하다.
어차피 최대 한바퀴 돌아가므로, n이상의 공간에 첫번째 초밥부터 다시한번 배치시킨다.
만약 1 2 3 초밥이 있었다면
1 2 3 1 2 3 을 만들어서, 2번부터 3연속으로 먹을시, 2 3 1 초밥을 먹을 수 있게 세팅한다.

초밥을 먹는다.

쿠폰을 이용한 초밥은 항상 먹고 시작한다.

초밥을 먹되, 해당 종류의 초밥을 지금까지 몇개나 먹었는지 기록한다.
그리고 해당 종류의 초밥을 이전에 먹은적이 있는지 확인한다.

초밥을 뱉는다.

연속으로 먹을 수 있는 초밥의 개수를 넘은경우 가장 먼저 먹은 초밥을 뱉는다.
뱉은 뒤 해당 종류의 초밥을 지금까지 몇개나 먹었는지 확인한다.

코드

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
#define MAX_dishes 3000001
using namespace std;
int n, d, k, c;

int dishes[MAX_dishes * 2];
int ate[3001];
int ate_num;
int ate_values;
int answer;

void eat(int shushi) {
	if (ate[shushi]==0){
		ate_values++;
		answer = max(answer, ate_values);
	}
	ate[shushi]++;
}

void overeat(int shushi) {
	ate[shushi]--;
	if (ate[shushi] == 0) {
		ate_values--;
	}
}

void solve() {
	for (int i = 0; i < n * 2; ++i) {
		if (i >= k) {
			overeat(dishes[i - k]);
			eat(dishes[i]);
		}
		else eat(dishes[i]);
	}
	cout << answer;
}

void input() {
	cin >> n >> d >> k >> c;
	ate[c]++;
	ate_values = 1;
	answer = 1;

	for (int i = 0; i < n; ++i) {
		cin >> dishes[i];
		dishes[n + i] = dishes[i];
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    //freopen("input.txt", "r", stdin);

	input();
	solve();

	return 0;
}

피드백

없음.