마구간 정하기 (결정 알고리즘) 파이썬
- N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3 .... 개의 좌표를 가지며, 마구간간에 좌표가 중복되는 일은 없다
- 현재 C마리의 말을 가지고 있는데, 이 말들이 서로 가까이 있는 것을 좋아하지 않는다
- 각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶다
- C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대 값을 출력하는 프로그램
- 결정 알고리즘의 핵심은 시작과 끝을 정하여 최적의 답을 구하는 것이다
- 이 문제에서 최적에 값을 구하기 위해서는 시작값과 끝값을 더해서 2로 나눈 뒤 중간값으로 설정한 뒤 앞 뒤로 최적의 값을 구해나가면 된다
n, c = map(int, input().split())
#마구간의 개수 -> n
#말의 수 -> c
Line = []
for _ in range(n):
tmp = int(input())
Line.append(tmp)
Line.sort()
#마구간의 번호를 받은 값을 tmp에 넣어서 Line에 넣어준 뒤 정렬해줌
lt = 1
rt = Line [n-1]
#결정 알고리즘의 핵심인 시작과 끝을 정해준다
while lt <= rt:
mid= (lt+rt)//2
if Count(mid) >= c :
res = mid
lt = mid+1
else:
rt=mid-1
#시작값과 끝값을 더해서 2로 나눈 뒤 중간값으로 설정한 뒤 앞 뒤로 최적의 값을 구한다
#else문을 입력해줘서 if 문이 돌수있는 환경을 만들어줌
print(res)
def Count(len):
cnt =1
ep =Line[0]
for i in range(1, n):
if Line[i] - ep >= len:
cnt += 1
ep=Line[i]
return cnt
#시작점과 그 다음오는 배열의 값을 계산하여 len 값보다 크거나 같으면 cnt++해줌
#ep를 바꿔주어 다음배열과 다다음배열과 계산해줌
#말의 개수를 리턴!
- 결정 알고리즘은 같은 매커니즘을 가지고 있지만 연습이 없으면 안되는 문제이다
- 매커니즘을 잘 알자!ㅍ
댓글