문제
https://www.acmicpc.net/problem/2531
접근방법
앞서 사용했던 투 포인터를 사용했다. 투 포인터가 은근히 많이 쓰이나보다.
회전 초밥이기 때문에, 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;
}
개선할 점
수월하게 풀려서 다행이었다! 투 포인터는 앞으로도 기억해야겠다.
'코딩테스트 준비 > 백준' 카테고리의 다른 글
[백준 17070] - 파이프 옮기기 1(DP) C++ (2) | 2024.03.15 |
---|---|
[백준 14719] - 빗물 c++ (1) | 2024.02.13 |
[백준 17615] - 볼 모으기 c++ (1) | 2024.02.13 |
[백준 20922] - 곂치는 건 싫어 c++ (1) | 2024.02.13 |
[백준 14940] - 쉬운 최단거리 c++ (1) | 2024.02.13 |