백준 15961번 회전 초밥 [C++]

https://www.acmicpc.net/problem/15961

15961번: 회전 초밥

 

 

 

#문제 해결 방법

슬라이딩 윈도우를 사용하자

#전체 코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N, d, k, c;
    cin >> N >> d >> k >> c;

    vector<int> sushi(N);
    vector<int> sushiCount(d + 1, 0);  

    for (int i = 0; i < N; i++) {
        cin >> sushi[i];
    }

    int sushiType = 0;
    int maxType = 0;

    for (int i = 0; i < k; i++) {
        if (sushiCount[sushi[i]]++ == 0) {
            sushiType++;
        }
    }

    maxType = sushiType;

    for (int i = 1; i < N; i++) {
        if (--sushiCount[sushi[i - 1]] == 0) {
            sushiType--;
        }

        if (sushiCount[sushi[(i + k - 1) % N]]++ == 0) {
            sushiType++;
        }


        if (sushiCount[c] == 0) {
            maxType = max(maxType, sushiType + 1);
        }
        else {
            maxType = max(maxType, sushiType);
        }
    }

    cout << maxType;

    return 0;
}

#코드 해설

 

1. 변수 초기화
   • N: 벨트 위에 놓인 접시의 수.
   • d: 초밥의 종류 수.
   • k: 연속해서 먹는 접시의 수.
   • c: 쿠폰에 적힌 초밥 번호.
   • sushi: 벨트 상의 초밥의 정보를 저장하는 벡터.
   • sushiCount: 각 초밥 번호가 현재 선택된 범위 내에서 몇 번 나타났는지를 저장하는 벡터.
   • sushiType: 현재 선택된 범위 내에서의 서로 다른 초밥의 종류 수.
   • maxType: 가능한 최대 종류의 초밥 수.
2. 처음 k개의 초밥 종류 계산
   • 초기에 0번부터 k-1번째 까지의 초밥을 선택한 상태에서의 서로 다른 종류의 초밥 수를 계산합니다.
3. 슬라이딩 윈도우를 사용한 계산
   • 회전 초밥 벨트이므로, N번을 반복하면서 슬라이딩 윈도우 기법을 사용하여 선택 범위를 1칸씩 옮겨가면서 서로 다른 종류의 초밥 수를 계산합니다.
   • 이때, 이전 범위의 첫번째 초밥을 제거하고, 새로운 초밥을 범위에 포함시키면서 선택된 범위 내에서의 서로 다른 초밥의 종류 수를 업데이트 합니다.
   • 또한, 현재 선택된 범위 내에서 쿠폰에 적힌 초밥 번호 c가 없으면, 쿠폰을 사용하여 추가로 1종류의 초밥을 먹을 수 있음을 고려하여 maxType을 업데이트합니다.
4. 결과 출력
   • maxType을 출력합니다. 이 값은 연속해서 k개의 접시를 먹었을 때, 가능한 한 최대의 다양한 종류의 초밥을 먹는 경우의 초밥 종류 수를 나타냅니다.