https://www.acmicpc.net/problem/14465
문제분석
- 분류
- 투포인터
- 슬라이딩 윈도우
- 문제설명
- 횡단보도의 개수 N개 입력
- 고장난 신호등의 개수 B개 그리고 좌표 입력
- 탐색하고자 하는 길이 K 입력
- 배열의 길이가 가변적일 때: 투 포인터, 배열의 길이가 고정적일 때: 슬라이딩 윈도우
- 슬라이딩 윈도우 -> O(N)의 속도로 탐색
입력
10 6 5
2
10
1
5
9
출력
1
코드
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int N, K, B;
cin >> N >> K >> B;
//횡단보도는 N개
vector<int>cross(N);
//고장난 신호등의 개수 B
for (int x = 0; x < B; x++)
{
int tmp;
cin >> tmp;
cross[tmp-1]++;
}
//탐색해야하는 길이 K
int broken = 0;
for (int x = 0; x < K; x++)
{
broken += cross[x];
}
//슬라이딩 윈도우로 고장난 창문의 최소값을 구한다.
int Min = broken;
for (int x = 0; x <= N - K; x++)
{
broken -= cross[x];
broken += cross[x+K];
if(Min > broken) Min = broken;
}
cout << Min;
return 0;
}
문제풀이
- 탐색해야 하는 도로의 길이는 일정하다. 탐색 배열의 길이가 고정되어 있다. -> 슬라이딩 윈도우 알고리즘을 활용한다.
- 횡단보도는 N개 있다. -> 전체 배열의 길이는 N이다. vector<int>cross(N);
- 고장난 신호등의 개수는 B개 이다. -> B번 반복문을 실행하여, 고장난 신호등의 정보를 입력한다.
- 신호등이 연속적으로 K개 작동해야 한다. -> 0 ~ K 까지의 배열의 고장난 신호등 개수를 탐색한다.
- 각 구간의 고장난 신호등의 개수 중에서 최소값이 정답이다.
'Koala - 7기 > 코딩테스트 준비 스터디' 카테고리의 다른 글
[백준 / c++ ] 7795 먹을 것인가 먹힐 것인가 (0) | 2022.07.24 |
---|---|
[백준 / Python] 21608번 상어 초등학교 (0) | 2022.07.24 |
[백준/python] 17135 캐슬 디펜스 (0) | 2022.07.24 |
[백준/Python] 7795번 먹을 것인가 먹힐 것인가 (0) | 2022.07.24 |
[백준/Python] 15686번 치킨 배달 (0) | 2022.07.24 |