.PNG)
25.마구간 정하기(결정알고리즘)
N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ......, xN의 좌표를 가지며, 마구간간에 좌표가 중복되는 일은 없습니다.
현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다.
각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을
마구간에 배치하고 싶습니다.
C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력하는 프로그램을 작성하세요.
▣ 입력설명
첫 줄에 자연수 N(3<=N<=200,000)과 C(2<=C<=N)이 공백을 사이에 두고 주어집니다.
둘째 줄부터 N개의 줄에 걸쳐 마구간의 좌표 xi(0<=xi<=1,000,000,000)가 한 줄에 하나씩
주어집니다.
▣ 출력설명
첫 줄에 가장 가까운 두 말의 최대 거리를 출력하세요.
▣ 입력예제 1
5 3
1 2 8 4 9
▣ 출력예제 1
3
<내 풀이> - 오답
res=0
g=[]
n, c = map(int, input().split())
for i in range(n) :
distance=int(input())
g.append(distance)
g.sort()
def Count(x) :
interval=0
cnt=1
for i in range(1,len(g)) :
interval+=g[i]-g[i-1]
if interval > x :
cnt+=1
interval=g[i]-g[i-1]
return(cnt)
lt=1
rt=max(g)-min(g)
while lt<=rt :
mid=(lt+rt)//2
if Count(mid)<=c:
res=mid
rt=mid-1
elif Count(mid)>c:
lt=mid+1
print(res)나의 의도는 우선
일단 c개의 말들을 넣기 위해 보장되어야 할 최소한의 간격-res을 구하고
(이를 위해서 cnt가 c이상이면 너무 간격이 좁은거고 c이하면 간격이 너무 넓은 것)
이 간격을 활용해서 답을 구하는 거였다.
근데 둘 사이에 보장되어야 할 최소한의 간격은 res로 찾았는데 이를 활용해서 가장 가까운 값의 최대값을 구하는 과정을 찾지 못했다 근데 사실 이 res도 잘못 구한 것 같다
=====> res구하는 것도 틀리고, res=mid설정할 때 부분도 잘못했다
-나의 res는 처음에 interval을 0으로 설정
<풀이>
- mid는 가장 가까운 말의 거리
res=0
g=[]
n, c = map(int, input().split())
for _ in range(n) :
distance=int(input())
g.append(distance)
g.sort()
def Count(x) :
cnt=1
lastone=g[0] #가장 마지막 범위
for i in range(1,n) :
if g[i]-lastone >= x :
cnt+=1
lastone=g[i]
return(cnt)
lt=1
rt=max(g)
while lt<=rt:
mid=(lt+rt)//2 #mid는 항상 이 while문 안에 있어야지 lt,rt갱신되면서 mid도 갱신된다
if Count(mid) >= c: #넣을 수 있는 말의 수가 c이상이면 당연히 c마리의 말도 넣을 수 있어
res=mid
lt=mid+1
else : #Count(x)<c => 넣을 수 있는 말의 수가 c이하면 c마리의 말도 당연히 안들어감
rt=mid-1
print(res)
<반성점>
- 내가 잘못 이해한 부분 :
난 cnt, 배치가능한 말의 수가 c마리보다 크다면
간격이 너무 좁은 거라서 res가 될 수 없다고 생각했고
c마리보다 작으면 res가 되는데 너무 간격이 넓으니깐 좁혀줘야 겠다고 생각
BUT C마리보다 더 많이 배치할 수 있다면 C마리 배치 가능, 즉 cnt<c일때 res
반면
C마리보다 적게 배치가능하면 C마리 배치는 꿈도 못 꾸니깐 res아님 - 사고를 clear하게 하기
- 복습하고 암기하고 다시 풀어보며 익숙해지고 능숙해져야 한다
<배운 점>
-
결정 알고리즘 문제는 다 비슷비슷하나 구하고자 하는 것을 잘 파악하고
res로 설정할 것을 명확하게 두어야 한다, 얘가 기준값보다 클때 mid=res인지 아닌지 -
mid는 항상 이 while문 안에 있어야지 lt,rt갱신되면서 mid도 갱신
def Count(x) :
cnt=1
lastone=g[0] #가장 마지막 범위를 설정해주고 그 아이와 직접적으로 빼는 것 : 나는 순수한 간격들만 계산해서 문제가 원하고자 하는 바를 충족하지 못했었다
for i in range(1,n) :
if g[i]-lastone >= x :
cnt+=1
lastone=g[i]
return(cnt)
- lastone에 대한 사고
- cnt=1이다 처음 인덱스에 바로 놓이는 것이 좋으므로
<2회독 내풀이> - 오답
n, c =map(int, input().split())
a=sorted(list(map(int, input().split())))
lt=1
rt=max(a)
while lt<=rt:
sum=0
end=a[0]
cnt=1
mid=(lt+rt)//2
for i in range(1,n) :
sum+=a[i]-end
end=a[i]
if sum > mid :
cnt+=1
sum=0
if cnt< c :
rt=mid-1
else :
res=mid
lt=mid+1
print(res)
==>end가 갱신되는 건 매번이 아니고, 간격이 mid를 넘어갈 시에만
n, c =map(int, input().split())
a=[]
for _ in range(n):
t=int(input())
a.append(t)
a.sort()
lt=1
rt=max(a)
while lt<=rt:
end=a[0]
cnt=1
mid=(lt+rt)//2
for i in range(1,n) :
if a[i]-end > mid :
cnt+=1
end=a[i]
if cnt< c :
rt=mid-1
else :
res=mid
lt=mid+1
print(res)=> 두번째 수정한 건 이건데 자꾸 1씩 적게 나와서 원인을 파악해보니
if a[i]-end > mid 부분이 >=, 크거나 같다로 되어야 한다
간격이 mid랑 같아지기만 해도 거기에 말을 놓고 다시 새로운 간격을 찾아야 한다
- 만약 같아졌는데 넘어갔다가, 다음 애를 더해서 커졌을 때 걔를 마지막 간격인 end로 지정한다면 경우를 누락하는 것
- 꼭 간격이 같아지기만 해도 거기에 말을 놓고 cnt+=1하기
