안녕하세요,
재재입니다.
boj 1306 달려라 홍준 문제 풀이입니다.
BOJ 1306 달려라 홍준
(1) 문제 설명
분류 : 자료 구조, sliding window
출처 : https://www.acmicpc.net/problem/1306
N 개의 숫자와 M 의 시야거리가 주어집니다.
Index i를 기준으로,
$$ \pm (m-1) $$
거리에 존재하는 값중 max 값을 뽑아주면 됩니다.
(2) 풀이 도출
거리
$$ 2m-1 $$
만큼 진행하고 적당히 똑똑한 자료구조로 최댓값을 뽑고,
진행하면서 값을 추가한다음 갯수가
$$ 2m-1 $$ 이 되도록 유지해주면 됩니다.
여기서 갯수가
$$ 2m $$
이 되는 순간 자료구조에서 제외 시켜주면 되는데 제외된 값이 인덱스가 불가능한 거라면 제거해주면 됩니다.
이때, 적당히 똑똑한 자료구조는 Heap 으로 충분한 것을 알 수 있습니다.
(3) 정답 코드
BOJ 1306 달려라 홍준