백준

백준 2531 회전 초밥

콩순이냉장고 2021. 7. 2. 14:46

문제 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

 

궁금한점 혹은 모르는점 논리적인 오류등 어떤질문이든 댓글은 언제나 환영입니다.