BOJ 15961 - 회전 초밥

www.acmicpc.net/problem/15961

15961번: 회전 초밥

 

먼저 일반 배열을 사용해서 원형 초밥에 담긴 초밥 정보들을 저장하게 한다

원형 큐 대신에 배열을 사용할 수 있는것은 모듈러 연산을 적절히 잘 수행하면 마치 원형 큐 처럼 순회가 가능하기 때문이다. (아래 코드에서 arr[(i + k - 1) % n])

그 다음 k 개 연속으로 먹을수 있는 경우에 대해서 가짓수를 센다. 

다음으로 n 만큼 반복문을 돌리면서, 제일 먼저, 쿠폰에 해당하는 초밥을 먹었는지 확인해줘야한다 

(쿠폰은 문제에서 제시한대로, 무조건 추가로 먹을 수 있는 초밥이기 때문에 먹는게 가짓수를 늘리는데 도움된다) 

그 후, 먹은 초밥이면 값을 하나씩 줄이고, 먹은 초밥 정보에 포함되지 않은 종류의 초밥이라면 total 변수를 하나 줄인다. 

그리고 나서 원형 큐 처럼 돌리되, 다음 차례에 있는 초밥을 한번도 먹지 않았다면, 초밥 종류를 나타내는 변수인 total 을 하나 늘린다.

 

 

- c++

#include <bits/stdc++.h>
 
#define MAX_N 3000001
#define MAX_D 3001
 
using namespace std;
 
int N, D, K, C; // 초밥접시수, 가짓수, 연속해서 먹는 접시의 수, 쿠폰번호 
int arr[MAX_N]; // 초밥 정보를 담은 배열 (원형 큐 대신에 그냥 배열로) 
int visited[MAX_D]; // 먹은 초밥에 대해 처리하기 위해 사용되는 배열 
 
void solve() {
    int total = 0, max_num = 0; // 초밥 종류를 세는 변수, 최대 가짓수. 
    for (int i = 0; i < K; ++i) { // k 개의 접시를 돌면서, 각 초밥의 종류를 카운팅함. 
        if (!visited[arr[i]]) total++; 
        visited[arr[i]]++;
    }
    
    max_num = total;
    
    for (int i = 1; i < N; ++i) { // 먹는 갯수 카운팅 
        if (max_num <= total) {
            if (!visited[C]) max_num = total + 1; // 쿠폰 초밥을 먹지 않았을때 
            else max_num = total;  
        }
        
        visited[arr[i - 1]]--; // 해당 초밥에 담긴 갯수를 담는 배열이므로, 먹었기에 하나 줄임 
        if (!visited[arr[i - 1]]) total--; // 해당 초밥이 큐에 없을때, 종류를 하나 줄임 
        
        // (i + K - 1) % N 은 회전초밥이므로, 원형으로 순회시키기 위함임. 
        if (!visited[arr[(i + K - 1) % N]]) total++;  // 다음차례의 초밥을 한번도 먹지 않았으면 종류늘림. 
        visited[arr[(i + K - 1) % N]]++;
    }
    
    cout << max_num;
}
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N >> D >> K >> C;
    
    for (int i = 0; i < N; ++i) {
        cin >> arr[i];
    }
    
    solve();
    
    return 0;
}