[백준 15961번/c++] 회전 초밥

문제

주어진 조건에 따라 손님이 먹을 수 있는 초밥 가짓수의 최댓값

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

 

---

조건

• 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹으면, 주어진 쿠폰으로 초밥 하나를 무료로 제공받는다.
  • 만약 쿠폰에 적힌 번호에 해당하는 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다.

 

---

입출력

입력

첫 번째 줄: 아래에 적힌 4가지의 수가 빈 칸을 사이에 두고 주어진다. 

• 회전 초밥 벨트에 놓인 접시의 수 N ( 2<=N<=3,000,000)
• 초밥의 가짓수 d (2<=d<=3,000)
• 연속해서 먹는 접시의 수 k (2<=k<=3,000(k<=N))
• 쿠폰 번호 c (1<=c<=d)

두번째 줄

• N개의 줄에는 벨트의 한 위치부터 시작하여 회전 방향을 따라갈 때 초밥의 종류를 나타내는 1이상 d 이하의 정수가 각 줄마다 하나씩 주어진다.

 

출력

• 주어진 회전 초밥 벨트에서 먹을 수 있는 초밥의 가짓수의 최댓값을 하나의 정수로 출력

 

---

시간 초과 발생

처음 문제 접근 시, 회전 벨트의 첫번째에서 마지막까지 for문을 돌려 각 위치에서 k개의 개수만큼 또 for문을 돌려 먹게되는 초밥의 가짓수를 구하였다.

 

🤨

이렇게 구하니 2중 반복문이 되어
3,000,000*3,000=9,000,000,000 -> 약 90억
c++의 경우 1억이 약 1초가 소요되므로, 시간 초과가 발생할 수 밖에 없었다.

 

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int N, d, k, c;
bool freeSushi=false;
vector<int> belt;

int eatSushi(){
    int maxx=0;

    for(int i=0; i<belt.size(); i++){
        int cnt=0;
        set<int> s;
        for(int j=0; j<k; j++){
            s.insert(belt[(i+j)%N]);
        }
        cnt=s.size();
        if(s.find(c)==s.end()){
            cnt++;
        }
        if(cnt>maxx){
            maxx=cnt;
            if(maxx==k+1){
                break;
            }
        }
    }
    
    return maxx;
}

int main() {
	// freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

    int sushi;

    cin >> N >> d >> k >> c;
    for(int i=0; i<N; i++){
        cin >> sushi;
        belt.push_back(sushi);
        if(sushi==c){
            freeSushi=true;
        }
    }
    cout << eatSushi();
	
	return 0;
}

 

---

슬라이딩 윈도우 적용하기

 

생각해보면 결국 오른쪽으로 한칸씩 이동하는 것이므로

첫번째와 마지막 원소만 생각해주면 된다!

 

 

---

코드 구현

필요한 변수들

• 회전 벨트 위의 초밥 번호를 저장하는 belt 배열
• 번호에 해당하는 초밥을 몇 개 먹었는지 체크하는 check 배열
• 먹은 초밥 종류의 개수를 저장하는 kind 변수

 

코드 흐름

1. 맨 처음 k개 우선 체크
2. 반복문을 통해 옆으로 한칸씩 이동
   1. 이때, 맨 앞 원소는 제외시켜주고 맨 뒤 원소를 적용
   2. 먹으려고 하는 초밥 번호에 해당하는 check 배열의 값이 0이면 kind 변수도 1 증가
3. 가장 큰 kind 값이 답

 

---

성공 코드(내 코드)

#include <iostream>
#include <vector>
using namespace std;

int N, d, k, c;
int maxx=-1, kind=0;
vector<int> belt;
vector<int> check(3001, 0);

void eatSushi(){
    // 쿠폰 사용
    check[c]++;
    kind++; 

    // 처음 k개
    for(int i=0; i<k; i++){
        if(check[belt[i]]==0){
            kind++;
        }
        check[belt[i]]++;
    }

    // 슬라이딩 윈도우
    for(int i=0; i<N; i++){
        if(kind>maxx){
            maxx=kind;
        }

        // 맨 앞에거 제외
        check[belt[i]]--;
        if(check[belt[i]]==0){
            kind--;
        }

        // 뒤로 한칸 이동하며 가리키는 새로운 원소
        if(check[belt[(i+k)%N]]==0){
            kind++;
        }
        check[belt[(i+k)%N]]++;
    }
}

int main() {
	// freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

    int sushi;

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

    cout << maxx;
	
	return 0;
}

---

후기

슬라이딩 윈도우를 이용하여 시간 초과를 피하는 것이 핵심인 문제였다. 슬라이딩 윈도우는 컴네때 배운 개념인데, 알고리즘 문제에도 적용되니 반가웠다~!🐰