백준 s1 2531 회전 초밥 c++

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

2531번: 회전 초밥

 

문제

원형의 회전 초밥이 주어진다. k개의 접시를 연속으로 먹는다고 할 때, 손님이 먹을 수 있는 초밥 가짓수의 최댓값은?

이때 쿠폰으로 c번 초밥은 먹을 수 있다.

 

풀이

배열의 어떤 연속적인 상태를 고려할 때, 한 칸씩 +- 가능할 땐 투포인터 사용 가능

 

st, en : 시작점과 끝점

cnt : 해당 st ~ en에 몇 가지의 초밥을 먹을 수 있는지

ans : cnt 값들의 최댓값

check[3005]: i번 초밥이 몇 개인지

 

쿠폰으로 먹을 수 있는 c번 초밥은 미리 체크를 해둔다.

 

수도 코드

//1. 맨 처음 상태
st = 0 en = k-1
cnt = 1 // 쿠폰은 미리 포함

for(맨 처음 st ~ en)
	check[초밥]++
    if check[초밥]이 0 -> 1로 증가 == 없다가 새로 생길 경우
    	cnt++ // 가짓수++
ans = cnt

//2. 회전 초밥 돌리기

for i: 0 ~ N // 배열에서 i번째 초밥(st)을 뺌
	check[st번 초밥] --
    if check[st번 초밥] 1 -> 0 // 있다가 없어졌을 경우
    	cnt-- // 가짓수 -1
    st++ // 한 칸 옮기기
    
    en++
    if en >= N 이면 en = 0으로 옮겨주기
    check[en번 초밥]++
    if check[en번 초밥]이 0 -> 1로 증가했으면
    	cnt++
        
    ans = max(ans, cnt) // 변동된 cnt로 max값과 비교

 

전체 코드

/*boj s1 2531 회전 초밥*/
#include <iostream>
#define MAXN 30005
using namespace std;

int N, d, k, c;

int arr[MAXN];
int check[3005]; // i번 초밥의 개수
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> d >> k >> c;
    for (int i = 0; i < N; i++)
        cin >> arr[i];

    // 1. 맨 처음 상태
    int st = 0;
    int en = st + k - 1;
    int cnt = 1; // 쿠폰은 미리 체크
    int ans = 0;
    check[c] = 1;
    for (int i = st; i <= en; i++) {
        check[arr[i]]++;
        if (check[arr[i]] == 1) cnt++; // 0 -> 1이 된 경우 cnt++
    }
    ans = cnt;

    for (int i = 0; i < N; i++) { // i번째 st를 뺌
        check[arr[st]]--;
        if (check[arr[st]] == 0) cnt--;
        st++;

        en++;
        if (en == N) en = 0;
        check[arr[en]]++;
        if (check[arr[en]] == 1) cnt++; // 0 -> 1이면

        ans = max(ans, cnt);
    }

    cout << ans << "\n";
}