728x90
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXNQOb3avD0DFAXS
문제 이해 자체는 어렵지 않다. 만약 답을 구할 수 있도록 러프하게 구해보면
1 3 4 5
라고 들어온다고 가정할 때 1에서 시작해서 N 모두 보기 , 2에서 시작해서 모두보기 해서 총 N * N의 시간이 걸리도록 하는 것은 쉽다.
그러나 20만 * 20만 = 4천억으로 어림도없다.
그래서 처음 생각해낸 것은 1 3 4 5에서 1에서 최고수를 구하고 3에서 최고수를 구하는 것을 이분탐색으로 찾아내는 식으로 문제를 풀었다. 예제는 맞았지만 시간초과가 발생했다.
N log N 으로도 풀어낼 수 없었다.
그래서 구글링을 해보니 이 문제는 이분탐색의 투포인터문제였다.
투포인터는 개념자체는 알고있긴한데 언제 사용해야할지 정확히 모르겠다.
#include <iostream>
#include <vector>
using namespace std;
bool isStudy[1000001];
int n, p;
void init(){
for(int i = 0; i < 1000001; i++) isStudy[i] = false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T; cin >> T;
for (int t = 1; t <= T; t++) {
init();
cin >> n >> p;
int isMax = 0;
for (int i = 0; i < n; i++) {
int tmp;
cin >> tmp;
isMax = max(isMax, tmp);
isStudy[tmp] = true;
}
int hi = 1;
int lo = 1;
int point = p;
int answer = p + 1;
while (hi < isMax + 1) {
if (isStudy[hi]) {
hi++;
answer = max(answer, hi - lo);
}
else if (point > 0) {
point--;
hi++;
}
else if (point == 0) {
answer = max(answer, hi - lo);
if (isStudy[lo] == false) point++;
lo++;
}
}
cout << '#' << t << ' ' << answer << '\n';
}
}
'SWEA' 카테고리의 다른 글
SWEA - 백만 장자 프로젝트 (C++) (0) | 2024.05.18 |
---|---|
SWEA - 증가하는 사탕 수열 (C++) (0) | 2024.05.17 |
SWEA - 공평한 분배2 (0) | 2024.05.16 |
SWEA - 10806번 수 만들기 (C++) (0) | 2024.01.19 |
SWEA - 햄버거 다이어트 (C++) (1) | 2023.12.15 |