[백준 2531] 회전초밥

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

2531번: 회전 초밥

#include <stdio.h>
int N, d, k, c;	//접시 수, 초밥의 가짓수, 연속해서 먹는 접시 수, 쿠폰번호
int susi[30000 + 10];
int diff[3000 + 10];
int max;
int flag;

void input(void)
{
	scanf("%d %d %d %d", &N, &d, &k, &c);
	for (int i = 0; i < N; i++) {
		scanf("%d", &susi[i]);
	}
}

void init(void)
{
	for (int i = 1; i <= d; i++) {
		diff[i] = 0;
	}
}

void get_max(void)
{
	for (int i = 0; i < N; i++) {
		for (int j = i; j <= (i + k - 1); j++) {	//연속으로 k개의 접시를 먹는다. 
			diff[susi[j % N]] += 1;		//인덱스가 범위를 벗어나지 않도록 %N
		}
		diff[c] += 1;	//쿠폰의 초밥은 무조건 먹을 수 있음 

		int cnt = 0;
		for (int j = 1; j <= d; j++) {
			if (diff[j] >= 1) cnt++;
		}
		if (max < cnt) max = cnt;
		init();	//diff배열 초기화
	}
}

int main(void)
{
	input();
	get_max();
	printf("%d", max);
	return 0;
}

흠.. 구현해놓고보니 간단하지만, 이 문제도 꽤나 짱구를 굴려야 했다. 

 

 

//get_max 함수

일단 이 문제는 손님이 먹을 수 있닌 초밥 가짓수의 최댓값을 구해야 한다. 

(1.) 조건으로 인해 k개의 접시를 연속으로 먹으면 쿠폰을 받아 한 개의 초밥을 더 먹을 수 있다. 따라서 두번째 포문에서 인덱스 j = i부터 j = (i + k - 1)까지 탐색한 것이다.

만약 7번 접시의 초밥을 먹었다면, diff 라는 배열의 7번 인덱스에 1개 먹었다고 표시해준다(즉,  j == 7 이고 diff[j] == 1). 그 다음에 또 한번 7번 접시의 초밥을 먹었다면, diff 배열의 7번 인덱스에 1을 또 더해준다(즉,  j == 7 이고 diff[j] == 2). diff를 방문을 표시하는 배열이라고 생각하면 쉬울 것 같다. 

다음으로 diff 배열의 원소가 1이상이면 해당 인덱스의 접시를 먹은 것 이므로 cnt를 올려준다. 그리고 max 값과 비교하여 cnt값이 크면 갱신해준다. 

 

 

//init 함수

이때 중요한 것이 diff 배열을 초기화해주는 init 함수이다. i 값(연속으로 k개의 접시를 먹는다고 할 때 가장 처음 위치)이 갱신됨에 따라 몇 개의 초밥을 먹을 수 있는지를 새롭게 탐색해야 한다. 

따라서 인덱스를 갱신하기 전에 diff 배열의 모든 원소를 0으로 만들어야 한다.