[개쉬운 풀이] 백준 2531 회전 초밥

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

문제

회전 초밥 음식점에는 회전하는 벨트 위에 여러 가지 종류의 초밥이 접시에 담겨 놓여 있고, 손님은 이 중에서 자기가 좋아하는 초밥을 골라서 먹는다. 초밥의 종류를 번호로 표현할 때, 다음 그림은 회전 초밥 음식점의 벨트 상태의 예를 보여주고 있다. 벨트 위에는 같은 종류의 초밥이 둘 이상 있을 수 있다.

새로 문을 연 회전 초밥 음식점이 불경기로 영업이 어려워서, 다음과 같이 두 가지 행사를 통해서 매상을 올리고자 한다.

원래 회전 초밥은 손님이 마음대로 초밥을 고르고, 먹은 초밥만큼 식대를 계산하지만, 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공한다.
각 고객에게 초밥의 종류 하나가 쓰인 쿠폰을 발행하고, 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종류의 초밥 하나를 추가로 무료로 제공한다. 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다.
위 할인 행사에 참여하여 가능한 한 다양한 종류의 초밥을 먹으려고 한다. 위 그림의 예를 가지고 생각해보자. k=4이고, 30번 초밥을 쿠폰으로 받았다고 가정하자. 쿠폰을 고려하지 않으면 4가지 다른 초밥을 먹을 수 있는 경우는 (9, 7, 30, 2), (30, 2, 7, 9), (2, 7, 9, 25) 세 가지 경우가 있는데, 30번 초밥을 추가로 쿠폰으로 먹을 수 있으므로 (2, 7, 9, 25)를 고르면 5가지 종류의 초밥을 먹을 수 있다.

회전 초밥 음식점의 벨트 상태, 메뉴에 있는 초밥의 가짓수, 연속해서 먹는 접시의 개수, 쿠폰 번호가 주어졌을 때, 손님이 먹을 수 있는 초밥 가짓수의 최댓값을 구하는 프로그램을 작성하시오.

생각

-- 초기생각 --

1. 벡터와 인덱스를 통해 원형 리스트를 구현한다.
2. 모든 경우의 수를 모두 해보고 (브루트포스) 그 중에서 max를 찾는다.
3. 초밥의 종류 d가 주어졌으므로, 초기 배열을 선언하고 bool을 통해 이미 먹은 초밥인지 계산한다.

-- 이후생각 --

1. vector보다는 set을 이용하여 구현하려고 했다.
2. 그러나 최대의 초밥 개수는 쿠폰인 C를 사용해야 하고 중복되는 초밥이 존재할 때, set은 같은 종류의 모든 초밥을 제거하기 때문에 어려움이 있다.
3. 따라서 map을 이용하여 슬라이싱 윈도우를 통해 구현하였다.

풀이

1. map을 통해 초기 초밥들을 0~k-1 만큼 넣는다 (k개의 접시) <- init
2. 이후 k 인덱스 부터, 초밥을 넣고 idx-k에 해당하는 초밥을 제거한다.
3. 이때 만약 초밥의 갯수가 현재 1이라면 m[idx] -= 1이 아닌 아예 제거를 해준다. (0은 초밥이 없다는 뜻이므로 size를 통해 갯수를 구하기 위해 제거한다.)
4. map.size()를 통해 현재 초밥의 종류 갯수를 알 수 있다. (map은 중복된 키값을 허용하지 않는다.)
5. answer와 비교하면서 최대값을 찾는다.
6. 초기 init에 사용된 0 ~ k-1 범위도 2번부터 5번까지의 과정을 진행해준다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#define endl '\n'
using namespace std;

//접시의 수 : N
//초밥의 가짓수 : d
//연속해서 먹는 접시의 개수 : k
//쿠폰번호 : c
int N, d, k ,c;
vector<int> belt;
map<int,int> m;

void input(){
    cin >> N >> d >> k >> c;
    int sushi;
    for(int i = 0; i < N; i++){
        cin >> sushi;
        belt.push_back(sushi);
    }
}

//슬라이싱 윈도우로 초밥이 포함되고 제거되는 과정
int process(int nextSushi, int lastSushi){
    m[nextSushi] += 1;
    if(m[lastSushi] == 1) m.erase(lastSushi);
    else m[lastSushi] -= 1; //초밥의 개수가 0이면 map에서 삭제해주어야함
    return m.size(); //초밥 종류의 갯수를 의미
}

void sol(){

    m[c] = 1; //최대는 쿠폰을 활용한 경우

    //init
    for(int i = 0; i < k; i++){
        m[belt[i]] += 1;
    }
    int answer = m.size();
    int nextSushi, lastSushi;

    //탐색
    for(int i = k; i < N; i++){
        nextSushi = belt[i];
        lastSushi = belt[i-k];
        answer = max(answer, process(nextSushi, lastSushi));

    }
    //남은 바퀴
    for(int i = 0; i < k; i++){
        nextSushi = belt[i];
        lastSushi = belt[N+i-k];
        answer = max(answer, process(nextSushi, lastSushi));
    }

    cout << answer << endl;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    input();
    sol();

    return 0;
}