[백준 2531] 회전 초밥

슬라이딩 윈도우 문제이다

보통 전체 원소 개수 N 탐색 범위 M이라고 하면

총 O(N*M)이 걸리는데 이걸 줄일 수 있다

 

일단 슬라이딩 윈도우의 특징은 한번 검사할때 범위가 M이라고 하면

다음 턴에는 총 두 개의 원소만 바뀐다는 것이다

맨 앞에꺼가 삭제되고 맨 뒤+1인 원소만 추가된다는 것이다

즉 맨 앞에꺼 뺀 M-1개의 원소는 그대로인 것이다

 

이런 dp스러운 성질을 이용해서 O(N)으로 줄일 수 있다

dp스럽다는게 굳이 매 경우마다 이미 계산한

저 두 개 사이에 있는 원소를 계산하지 않아도 된다는 것이다

여기서 보면 구간이 5이므로 총 전꺼랑 다음꺼랑 총 4개가 겹치는거다

이 그림에서는 3 2 6 -1이 겹치는거임

이건 그럼 이미 전에 계산한건데 또 계산할 필요가 없음

그래서 dp 같다는거임

dp가 그 전에 계산한걸 또 계산하지 않으려고 있는거니까

 

아래 코드는 이 문제가 0ms 안에 풀었길래 봐서 안 답안이다

아래처럼 푸는게 당연히 좋다

 

#include <iostream>

#define SIZE 30000

using namespace std;

int sushi[SIZE];
int window[3001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
    int n, d, k, c;
    cin >> n >> d >> k >> c;

    for (int i = 0; i < n; i++) cin >> sushi[i];

    int total = 0;
    int maxTypes = 0;

    // 처음 시작일때만 window 배열 초기화
    for (int i = 0; i < k; i++) {
        if (window[sushi[i]] == 0) total++;
        window[sushi[i]]++;
    }

    // 쿠폰 종류는 예외
    window[c]++;
    if (window[c] == 1) total++;
    maxTypes = total;

    for (int i = 0; i < n; i++) {
        // 한 칸 움직이면서 이제 안먹는 스시일때
        // 만약 해당 스시가 1개 밖에 없었으면 즉 이제 없어질 종류면 전체종류에서 빼주기
        if (window[sushi[i]] == 1) total--;
        window[sushi[i]]--;

        // 한 칸 움직이면서 새로 먹는 스시일때
        // 만약 해당 스시 종류가 없었으면 전체종류에서 추가해주기
        if (window[sushi[(i + k) % n]] == 0) total++;
        window[sushi[(i + k) % n]]++;

        // 각 구간마다 maxTypes 최신화
        maxTypes = max(maxTypes, total + (window[c] == 0 ? 1 : 0));
    }

    cout << maxTypes << "\n";
    return 0;
}

 

---

 

이건 내 첫번째 풀이

#include <iostream>
#include <vector>
#include <bitset>

#define SIZE 30000

using namespace std;

int sushi[SIZE];
bitset<3001> check;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N, d, k, c;
	cin >> N >> d >> k >> c;

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

	int ans = -1;
	for (int i = 0; i < N; i++) {
		check.reset();
		check[c] = 1;
		for (int j = 0; j < k; j++) {
			check[sushi[(i + j) % N]] = 1;
		}
		int cnt = check.count();
		ans = max(ans, cnt);
	}
	cout << ans;
}