[알고리즘 스터디] 백준 #2531 회전초밥

[문제]

회전하는 벨트 위에 위와 같이 초밥들이 있다. 벨트 위에는 같은 종류의 초밥이 여러개 있을 수 있다.

손님은 초밥을 골라서 먹을 것이다. 

1. 연속으로 k접시를 먹을 경우, 할인된 가격을 지불한다.

2. 각 고객에게 초밥 종류 중 하나가 쓰여진 쿠폰을 발행하고, 손님이 1번 행사에 참가할 경우 해당 초밥 1접시를 무료로 제공한다. 벨트 위에 해당 초밥이 없을 경우 새로 만들어 제공한다.

손님은 위의 행사에 참여하여 최대한 다양한 종류의 초밥을 먹으려고 한다. 

 

[input]

벨트에 놓인 접시의 수 N ( 2 ≤ N ≤ 30000 )

초밥의 가짓수 d ( 2 ≤ d ≤ 3000 )

연속해서 먹는 접시의 수 k ( 2 ≤ k ≤ 3000 (k ≤ N) )

쿠폰번호 c ( 1 ≤ c ≤ d )

 

N d k c

초밥 종류 (한줄씩)

 

[output]

주어진 회전 초밥 벨트에서 먹을 수 있는 초밥 가짓수의 최댓값

 

[풀이]

첫 번째.

count 와 kind배열을 만들어서 이용하자.

count  = [start~c가 나올 때 까지 접시 개수, ... , c~c 접시 개수, ... , c~end 접시 개수]

kind = [start~c가 나올 때 까지 초밥 종류, ... , c~c 초밥 종류, ... , c~end 초밥 종류]

c=30

 

이렇게 하면 어떤 경우에서는 빠르게 output을 구할 수 있지만, 여전히 완전탐색을 해야하는 경우가 존재하였다. 

완전탐색의 경우 최악의 복잡도가 O(N*k) = 3000000 * 3000 = 90억 이므로 시간초과가 발생한다.

 

두 번째.(최종)

이 문제에 관해 조사하던 중 '슬라이딩 윈도우' 기법으로 풀어야 한다는 것을 알게되었다. 

지난번 스터디에서 나왔던 기법인데, 완전탐색과의 다른 점을 이해하지 못해 나중에 공부할 것으로 미뤄두었던 알고리즘이다. 

슬라이딩 윈도우는 윈도우가 미끄러지듯이 배열의 첫 부분 부터 끝 부분까지 탐색하는 알고리즘이다.

위의 입력을 예로들면 이런식으로 탐색하게 된다. 

 

여기까지만 보면 완전탐색과 무엇이 다른지 의문이 들기 시작한다.

슬라이딩 윈도우는 O(n)의 복잡도를 가지는데, 매번 k개의 접시를 모두 검사하지 않기 때문이다. 

- 방금 뺀 스시의 종류가 더 이상 윈도우에 없으면 count-=1

- 방금 새로 들어온 스시의 종류가 원래 윈도우에 없던 것이면 count+=1

- 현재의 윈도우 안에 c번(쿠폰)스시가 없을 경우 count+=1

해서 이전 윈도우의 count값과 비교하여 더 큰값으로 유지시켜서 끝까지 반복하면 된다.

한 윈도우 내의 연산이 상수번으로 끝나기 때문에 O(n)의 복잡도를 가지는 것이다. 

 

윈도우는 계속 맨 앞에 원소를 제거하고, 맨 뒤에 다른 원소를 추가하는 방식으로 연산되기 때문에 C++ STL queue 자료구조를 사용하였다. 

 

[최종 코드]

#include <stdio.h>
#include <algorithm> //max()를 위한 헤더파일 
#include <queue>
#include <memory.h> //memset을 백준에서 사용하기 위한 헤더파일
using namespace std;

int n, d, k, c;
int belt[3000000]; 
int kind[3000]; 
int i, j;
queue<int> window;

int slidingWindow() {
	int maxcount;
	int count = 0;
	int temp;
	for (int i = 0;i < k;i++) {
		temp = belt[i];
		window.push(temp);
		if (kind[temp - 1] == 0)
			count++;
		kind[temp - 1]++;
	}
	if (kind[c - 1] == 0)
		maxcount = count + 1;
	else
		maxcount = count;
	for (int i = k;i < n+k;i++) {
		int tempcount = count;
		//맨 앞에 있던 접시 확인 후 제거
		int front = window.front();
		kind[front - 1]--;
		if (kind[front-1]==0)
			tempcount--;
		window.pop();

		//새로운 접시 추가 
		temp = belt[i%n];
		window.push(temp);
		if (kind[temp - 1] == 0)
			tempcount++;
		kind[temp - 1]++;
		//쿠폰 초밥을 아직 먹지 않았을 때 
		if (kind[c - 1] == 0)
			maxcount=max(maxcount,tempcount+1);
		else
			maxcount = max(maxcount, tempcount);
	
		count = tempcount;
	}
	return maxcount;
}
int main() {
	memset(belt, 0, sizeof(belt));
	scanf_s("%d", &n);
	scanf_s("%d", &d);
	scanf_s("%d", &k);
	scanf_s("%d", &c);
	for (int i = 0;i < n;i++) {
		scanf_s("%d", &belt[i]);
	}
	printf("%d", slidingWindow());
}

[고려할 점]

1. slidingWindow()에서 for문을 돌릴 때, k~n-1까지가 아니라, n~n+k-1(n번)돌려야 하는 점이 중요

2. 우리가 사용하는 배열은 처음과 끝이 있는 모양이지만, 실제로 벨트 형태로 구성되어 있기 때문에 belt[i%n]로 접근하는 것이 중요

3. 쿠폰 초밥을 새로 만들어먹어야 하는지 아닌지는 매 window마다 다르기 때문에, tempcount에 더해버려서 넘기게 되면 다음 window가 영향을 받는다. 따라서 변수에 더하지 말고 if문을 이용해 아래와 같이 작성해야함

if (kind[c - 1] == 0)
    maxcount=max(maxcount,tempcount+1);
else
    maxcount = max(maxcount, tempcount);
count = tempcount;

슬라이딩 윈도우로 풀 수 있다는 것을 몰랐으면, 이틀밤을 새도 풀지 못했을 것 같은 문제였다.