코딩테스트 준비/백준

[백준 2531] - 회전 초밥 c++

SeoburiFaust 2024. 2. 13. 17:55

문제

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

 

2531번: 회전 초밥

첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤

www.acmicpc.net

접근방법

앞서 사용했던 투 포인터를 사용했다. 투 포인터가 은근히 많이 쓰이나보다.

회전 초밥이기 때문에, dishes배열을 2개 이어 붙였다.

배열 이어 붙이는 것이 아주 유용하게 쓰인다.

 

start와 end 포인터를 두고 그 사이에 있는 숫자들의 개수를 셌다.

그리고 while문이 돌 때마다 배열을 초기화했다.

 

flag는 범위 안에 쿠폰 번호가 있는 지 조회하려고 생성했다.

true인 경우 쿠폰번호에 해당하는 초밥 종류가 범위에 있는 것이고,

false인 경우는 없는 것이다. 없는 경우에는 count에 +1을 해준다.

코드

#include <iostream>
#include <vector>

using namespace std;


int main() {

    //단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ k ≤ 3,000 (k ≤ N), 1 ≤ c ≤ d
    int n, d, k, c;      //n : 접시개수, d : 초밥가짓수, k : 연속 접시 수, c : 쿠폰 번호
    cin >> n >> d >> k >> c;
    vector<int> dishes(n);
    for (int i=0;i<n;i++) {
        cin >> dishes[i];
    }
    for (int i=0;i<n;i++) {
        dishes.push_back(dishes[i]);
    }
    int start = 0;
    int end = k-1;
    int result = 0;
    while (end < dishes.size()) {
        int i = start;
        int count = 0;
        bool flag = false;
        vector<int> cnt(d+1, 0);

        while(i <= end) {
            if (dishes[i] == c) flag = true;
            if (cnt[dishes[i]]++ == 0) {
                count++;
            }
            i++;
        }
        if (flag) result = max(result, count);
        else result = max(result, count+1);
        start++;
        end++;
    }
    
    cout << result << endl;

    return 0;
}

 

 

개선할 점

수월하게 풀려서 다행이었다! 투 포인터는 앞으로도 기억해야겠다.