11973번 Angry Cows (Silver)
이왜틀?
11973번 Angry Cows (Silver) - 백준
아 이 문제 그거다.
골드 풀고 소스 그대로 집어넣었다가 틀린 문제.
골드랑 완전히 다른 문제라 틀린 문제다.
그냥 새로 풀어야한다는 뜻
번역
골드랑 비슷한데 조금 다르다.
소를 날리면 반지름 R 범위 내 건초더미를 폭발시킨다.
K마리의 소를 날려 N개의 건초더미를 터뜨릴때 필요한 힘 R의 최소 값을 구하는 문제.
설계
건초더미를 정렬해서 힘 R의 소를 날린다.
x위치에 떨어졌을 경우 x - R, x + R 건초더미를 터칠 때 K마리가 되는지 확인한다.
구현
정렬 후 이분탐색을 진행한다.
유효성 검증 시 제일 왼쪽 건초더미를 폭발의 제일 왼쪽 기준점으로 잡고 K마리 이하의 소가 필요한지 확인한다.
def isValid(R):
count = 0
idx = 0
while idx < N:
count += 1
# 힘 R로 터질 때 현재 건초더미를 제일 왼쪽으로 두고 2 * R 만큼 오른쪽
explode = haybales[idx] + (2 * R)
while idx < N and haybales[idx] <= explode:
idx += 1
# K마리 이하로 날렸으면 true
return count <= K
N, K = map(int, input().split())
haybales = [int(input()) for _ in range(N)]
haybales.sort()
left = 0
right = 1000000000
R = 0
while left <= right:
mid = (left + right) // 2
if isValid(mid):
R = mid
right = mid - 1
else:
left = mid + 1
print(R)
채점
2번 제출했는데 첫 번째 제출은 틀린 코드가 통과했다.
이분 탐색 범위를 haybales 범위로 잡아서 틀려야할 코드인데 테스트케이스가 부족했는지 통과해버렸다.
반례 데이터는 아래와 같다.
# Input
5 1
100
101
102
103
104
# Answer
2
# Output
100
반성
틀린 코드가 통과해서 자기 코드 저격해보는건 또 첫 경험이다.
신선하고 즐거운걸?
코드 확인