취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 15961번 문제인 회전 초밥이다.
문제는 아래 링크를 확인하자.

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

각 연속한 K개의 초밥과 쿠폰 C에 해당하는 초밥을 먹었을 때 먹을 수 있는 초밥의 종류의 최댓값을 구하는 문제이다.

하나의 길이 K 구간에서 각 초밥종류마다 먹은 개수와 그때 먹은 초밥의 가짓수를 구해두자.

이 구간에서 맨 앞의 초밥을 빼고 맨 뒤의 초밥 다음 초밥을 먹게 되면 그때 먹은 초밥의 종류는 다음과 같게 된다.

1) 맨 앞의 초밥을 빼서 그 초밥을 먹은 적이 없게 된다면(0개 먹은 상태가 된다면) 먹은 초밥의 가짓수에서 1을 뺀다.

2) 새로 먹은 초밥이 이전에 먹은 개수가 0개인 종류라면 먹은 초밥의 가짓수에 1을 더한다.

이를 한바퀴 돌면 문제를 해결할 수 있다.

필요한 만큼 배열의 앞쪽과 똑같은 배열을 원래 배열의 끝에 붙이면 원형으로 배치된 배열에서의 각 케이스를 쉽게 살펴볼 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int arr[3003000];
int bought[3001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int N, D, K, C; cin >> N >> D >> K >> C;
	for (int i = 0; i < N; i++) cin >> arr[i];
	for (int i = 0; i < K; i++) {
		arr[i + N] = arr[i];
	}
	int cnt = 1;
	bought[C] = 1;
	for (int i = 0; i < K; i++) {
		bought[arr[i]]++;
		if (bought[arr[i]] == 1) cnt++;
	}
	int ans = cnt;
	for (int i = 0; i < N; i++) {
		bought[arr[i]]--;
		if (!bought[arr[i]]) cnt--;
		bought[arr[i + K]]++;
		if (bought[arr[i + K]] == 1) cnt++;
		if (cnt > ans) ans = cnt;
	}

	cout << ans;
}