[S1] 백준 2531번 회전 초밥 C++ 슬라이딩 윈도우, 덱

리뷰

 

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

회전 초밥의 라인을 돌려가며 먹을 수 있는 초밥의 가짓수의 최대를 구하는 문제

N * k 는 9천만이라 쉽게 AC가 날 줄 알앗는데 덱 + set만으로 구현을 하니 시간초과가 났다 

 

전역 변수

• n : 주어지는 초밥의 개수
• d : 주어지는 초밥의 최대 가짓수
• k : 먹을 수 있는 초밥의 개수
• c : 추가로 얻을 수 있는 초밥의 정보
• ans : 먹을 수 있는 초밥의 최대 가짓수를 저장할 변수
• v : 먹은 각 초밥의 개수를 저장하기 위한 배열

 

함수

없음

 

 

문제풀이

1. n, d, k, c를 입력 받아주고 정수형 덱 deq를 초기화 해준다.
2. n개의 초밥 정보를 deq에 추가해 준다.
3. cnt를 0으로 초기화 하고, 처음 0 ~ k - 1개의 초밥을 먹은 상태로 만들어준다.
4. ans의 초깃값을 cnt로 초기화 해준다.
5. 이후 n번의 반복문을 돌려준다.
6. 0번 인덱스의 초밥을 먹은 초밥에서 빼주고 덱의 맨 뒤로 옮겨준다.
7. k - 1번 인덱스의 초밥을 먹은 초밥으로 추가해 준다.
8. 만약 c를 먹은 상태라면 ans를 cnt와 비교하여 더 큰값을 저장해 준다.
9. 만약 c를 먹지 않은 상태라면 ans를 cnt + 1과 비교하여 더 큰값을 저장해 준다.
10. ans에 저장된 값을 출력해 준다.

 

참고 사항

슬라이딩 윈도우는 고정해 놓고 덱을 통해 계속 초밥을 회전 시켜주었다.

 

 

정답 코드

#include<iostream>
#include<deque>
using namespace std;

int n, d, k, c, ans;
int v[30000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> d >> k >> c;
	deque<int> deq;
	for (int i = 0; i < n; i++) {
		int a; cin >> a;
		deq.push_back(a);
	};

	int cnt = 0;
	for (int i = 0; i < k; i++) {
		if (!v[deq[i]]) cnt++;
		v[deq[i]]++;
	}
	ans = cnt;

	while (n--) {
		if (v[deq[0]] == 1) cnt--;
		v[deq[0]]--;
		deq.push_back(deq.front());
		deq.pop_front();
		if (!v[deq[k - 1]]) cnt++;
		v[deq[k - 1]]++;
		if (v[c]) ans = max(ans, cnt);
		else ans = max(ans, cnt + 1);
	}
	cout << ans;
}