https://www.acmicpc.net/problem/10025
10025번: 게으른 백곰
첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다.
www.acmicpc.net
투 포인터, 슬라이딩 윈도우로 접근한 문제다.
풀이
투 포인터를 사용하여 곰이 얼음에 닿을 수 있는 최대거리 (2*k+1) 범위의 얼음합을 좌표값 0부터 1000,000까지 탐색을 하면 된다. 단 k의 크기가 500,000을 넘는다면 모든 좌표에 있는 얼음을 가져올 수 있으므로, 입력을 받으면서 얼음의 최댓값을 미리 계산하여 출력하면 된다.
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [15565] 귀여운 라이언 (0) | 2023.01.15 |
|---|---|
| [1337] 올바른 배열 (0) | 2023.01.14 |
| [14246] K보다 큰 구간 (0) | 2023.01.12 |
| [2018] 수들의 합 5 (0) | 2023.01.11 |
| [1504] 특정한 최단 경로 (0) | 2023.01.04 |