문제 URL : https://www.acmicpc.net/problem/2531
2531번: 회전 초밥
첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤
www.acmicpc.net
문제접근법 :
- n-k번째부터 n번째까지 전부 먹어놓습니다. 최대 k개의접시를 먹기위해
- 그다음 1번째부터 n번째까지 먹어보고 i-k번째를 버리면 그의 종류가 몇가지인지 확인합니다.
- 쿠폰으로 먹을수 없는 종류가 있다면 쿠폰을 더해서 하나더 만들어먹으니 꿀맛이겠죠?
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#include <bits/stdc++.h>
#include<unordered_map>
using namespace std;
vector<int> v;
int n, d, k, c;
void input() {
cin >> n >> d >> k >> c;
v.resize(n);
for (int i = 0; i < n; i++)
cin >> v[i];
}
void solve() {
unordered_map<int, int> visit;
int res = 0;
for (int i = n - k; i < n; i++) {
visit[v[i]]++;
}
for (int i = 0; i < n; i++) {
int j = (n + i - k) % n;
visit[v[i]]++;
visit[v[j]]--;
if (visit[v[j]] <= 0)
visit.erase(v[j]);
res = max(res, (int)visit.size() + (visit.count(c) == 0));
}
cout << res << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
return 0;
}
|
cs |
궁금한점 혹은 모르는점 논리적인 오류등 어떤질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 17609 회문 (0) | 2021.07.05 |
|---|---|
| 백준 5582 공통 부분 문자열 (0) | 2021.07.05 |
| 백준 20551 Sort 마스터 배지훈의 후계자 (0) | 2021.07.02 |
| 백준 1485 정사각형 (2) | 2021.07.02 |
| 백준 1331 나이트 투어 (0) | 2021.07.02 |
