[Python 3] BOJ 30459 현수막 걸기

이 문제는 지난 2학기 서강대 ICPC 동아리의 weekly session이였던 '주간 512'에서 봤던 문제였는데, 풀 시간도 없고, 해설은 들었지만 아이디어가 명확하지 않았어서 고민했던 문제였다.

 

https://www.acmicpc.net/problem/30459

30459번: 현수막 걸기

 

이 문제는 이분 탐색으로 해결하였다.

 

처음에는 어떤 걸 이분 탐색의 기준점으로 찾아야 할지 고민했는데, 왜냐하면 말뚝이 2000개 있기 때문에, 두 개의 말뚝이 밑변의 길이를 나타내기 때문에, 결국 약 400만가지의 말뚝 사이의 길이 (즉 밑변의 길이)가 가능 할 것이라고 생각했다.

 

하지만, 400만 가지의 말뚝 사이의 길이를 집합에 넣어서 중복을 제거하고, sort하였다.

 

이후 모든 깃대의 길이들에 대해서, 길이에 대하여 이분 탐색을 실시하였다.

 

 

코드는 다음과 같다.

 

 

n,m,r=map(int,input().split())
loc=list(map(int,input().split()))
length=list(map(int,input().split()))

loc.sort()
locations=[]
answer=-1
for i in range(n-1):
    for j in range(i+1,n):
        locations.append(abs(loc[j]-loc[i]))

locations=list(set(locations))
locations.sort()
for i in range(m):
    left=0
    right=len(locations)-1
    while left<=right:
        mid=(left+right)//2
        if locations[mid]*length[i]<=2*r:
            answer=max(answer,locations[mid]*length[i])
            left=mid+1
        else:
            right=mid-1

if answer!=-1:
    print("%.1f" %(answer/2))
else:
    print(-1)

 

마지막에 float 형식으로 출력해야한 다는 점, 유의해야겠다.