백준 2531번 회전초밥

문제 링크입니다: https://www.acmicpc.net/problem/2531

2531번: 회전 초밥

모듈러 연산을 잘 사용해야 하는 문제였습니다.

i = 0부터 탐색을 진행하기 때문에 0 이전 즉, (N - k) ~ (N - 1) 인덱스 내의 초밥의 종류 개수부터 구했습니다.(빨간 박스 참고)

이후부터는 (N - k) 번째에 속한 스시의 종류 개수를 1 감소하고 0 번째에 속한 초밥의 종류 개수를 1 증가시키며 result를 갱신했습니다.

또한, 쿠폰에 속한 스시의 종류가 현재 구한 체인 내에 없을 경우 더해줘야 합니다!

	#include <iostream>
	#include <vector>
	#include <algorithm>
	using namespace std;
	const int MAX = 3000 + 1;
	int sushiCnt[MAX];
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N, d, k, c;
	cin >> N >> d >> k >> c;
	vector<int> sushi(N);
	int acc = 0;
	for (int i = 0; i < N; i++)
	{
	cin >> sushi[i];
	// 이후 i = 0 부터 반복문을 돌릴 것이기 때문에
	// i = 0: (N - k) ~ (N - 1) 이내 스시 종류
	if (i >= N - k)
	{
	acc += (sushiCnt[sushi[i]]++ == 0);
	}
	}
	int result = 0;
	for (int i = 0; i < N; i++)
	{
	// 쿠폰에 속한 스시 유무 판별까지
	result = max(result, acc + (sushiCnt[c] == 0));
	acc += (sushiCnt[sushi[i]]++ == 0);
	acc -= (--sushiCnt[sushi[(i + N - k) % N]] == 0);
	}
	cout << result << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~