https://www.acmicpc.net/problem/15961
15961번: 회전 초밥
첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2
www.acmicpc.net
코드:
|
#include <iostream>
using namespace std;
int n, d, k, c, cnt, ans, l, r;
int lis[3030303], sushi[3030];
void input() {
cin >> n >> d >> k >> c;
for (int i = 0; i < n; i++) cin >> lis[i];
}
void solve() {
l = 0; r = k - 1;
for (int i = l; i <= r; i++) if (!sushi[lis[i]]++) cnt++;
if (!sushi[c]) ans = ans < cnt + 1 ? cnt + 1 : ans;
else ans = ans < cnt ? cnt : ans;
do {
if (!--sushi[lis[l++]]) cnt--;
if (!sushi[lis[++r %= n]]++) cnt++;
if (!sushi[c]) ans = ans < cnt + 1 ? cnt + 1 : ans;
else ans = ans < cnt ? cnt : ans;
} while (l != n);
}
int main() {
input();
solve();
cout << ans;
return 0;
}
|
cs |
풀이:
간단한 슬라이딩 윈도우 문제입니다
'백준(C, C++) > 골드' 카테고리의 다른 글
| 백준 14503: 로봇 청소기 [C/C++], 삼성 코딩 테스트 (0) | 2022.06.12 |
|---|---|
| 백준 3078: 좋은 친구 [C/C++] (0) | 2022.06.11 |
| 백준 7450: Bin Packing [C/C++] (0) | 2022.06.07 |
| 백준 2357 최솟값과 최댓값 c++ (0) | 2022.06.02 |
| 백준 11505 구간 곱 구하기 (0) | 2022.06.02 |