[BOJ 23830] 백준 23830번 - 제기차기

		SASA Programming Contest 2021 풀이
A		[BOJ 23825] SASA 모형을 만들어보자
B		[BOJ 23826] 와이파이
C1		[BOJ 23827] 수열 (Easy)
C2		[BOJ 23828] 수열 (Hard)
D		[BOJ 23829] 인문예술탐사주간
E		[BOJ 23830] 제기차기
F		[BOJ 23831] 나 퇴사임?
G		[BOJ 23832] 서로소 그래프
J1		[BOJ 23835] 어떤 우유의 배달목록 (Easy)

1. 문제

$23830$. 제기차기 (SASA Programming Contest 2021 Open Contest E번)

백준 23830번 - 제기차기 (https://www.acmicpc.net/problem/23830)

2. 풀이

$r$값은 고정이고 $K$값이 변화한다. 따라서 수직선 위에서 간격이 $r$로 고정되어 있는 $K\sim K+r$ 구간이 왼쪽 오른쪽으로 이동한다고 생각하면 된다. 전체 합을 구해 놓고 $K$ 미만인 점수 개수만큼 $q$를 더하고, $K+r$ 초과인 점수 개수만큼 $p$를 빼면 된다.

$K$와 $K+r$의 위치를 찾기 위해 이분탐색을 사용한다. 중복 값의 존재 때문에 $K$보다 작은 값을 찾기 위해 $K$에는 lower_bound를, $K+r$보다 큰 값을 찾기 위해 $K+r$에는 upper_bound를 사용해서 위치 값을 찾아야 한다.

$K$값에 대해서 이분탐색을 수행하여 각각의 $mid(K)$으로 만들어지는 점수와 $S$를 비교하는 작업을 통해 $K$로 가능한 최솟값을 찾아간다. 이때, $K$는 양의 정수라고 했으므로 가장 작은 값은 $(1)$, 어떤 값 기준 미만인 점수 개수를 세므로 가장 큰 값은 (제일 큰 점수$+1$)이다.

3. 채점 결과

4. 회고

중복 값을 생각하지 않고 $K$와 $K+r$ 모두 lower_bound를 사용해서 위치를 찾아서 WA를 받았다.

5. 코드