[이분탐색] 2110번, 1300번

1. 공유기 설치

링크 - 공유기 설치

아이디어

어떻게 이분탐색이 가능한 건지 이해가 가질 않았는데, 질문 게시판을 통해서 조금 감을 잡을 수 있었다.

참조 - https://www.acmicpc.net/board/view/8301

여태까지의 문제는 만약 거리를 구하는게 문제였다면 기준을 거리로 두어 푸는 문제였다.

이 문제는 거리를 구하라고 하고 있지만 이분 탐색의 기준을 공유기의 수로 사용해야 하는 문제였다.

참조2 - https://www.acmicpc.net/board/view/31633

거리를 mid로 두고, arr[curr]>= arr[prev]+mid 이면 공유기를 설치하는 방식으로 구현을 했다.

먼저 공유기를 설치한 후 , 공유기의 숫자가 c보다 작으면 설정한 거리가 너무 멀다는 뜻이므로 왼쪽 탐색을 하고, c보다 크면 설정한 거리보다 좁다는 뜻이므로 오른쪽 탐색을 하도록 했다.

코드

def binary_search(start,end):
    result =0
    while start<=end:
        mid = (start+end)//2
        current = arr[0]
        count=1
        for  i in range(1,len(arr)):
            if arr[i]>=current+mid:
                count+=1
                current=arr[i] #i번째에 공유기 설치
        if count>=c:
            result = mid #인접한 거리의 최댓값을 물었기 때문에 일단 result 저장을 함
            start = mid+1 #거리를 더 멀리 둔다.
        else:
            end = mid-1 #거리를 더 좁게 둔다. 
    return result

n,c = map(int,input().split())
arr=[]

for i in range(n):
    tmp = int(input())
    arr.append(tmp)
    
arr.sort()

print(binary_search(1, arr[-1]-arr[0]))

개수를 정하고 거리를 구하는 것이 아니라,
거리를 구하고 개수를 정하는 것이 포인트인 문제였던 것 같다.

2. K번째 수

링크 - 공유기 설치

안좋은 코드

n = int(input())
k = int(input())

B =[] #일차원 배열 B

for i in range(1,n+1):
    for j in range(1,n+1):
        B.append(i*j)

B.sort()

print(B[k-1])

가장 간단하게 생각할 수 있는 코드지만 시간 복잡도가 O(n^2)이기 때문에 통과를 못하는 코드이다.

아이디어

먼저 이차원 배열의 값들을 일차원 배열에 옮기면 안되는 것이 중요하다.

참조 - https://claude-u.tistory.com/449

오름차순 정렬을 하고 k번째 값을 구하라는 것은 B[k]보다 작은 값이 k개가 있다는 뜻이다.

참조 사이트에 있는 예시처럼, 배수,약수를 구해서 더해주면 되는 문제였다.

input	output
3	6
7

을 생각해보면
A배열
1 2 3
2 4 6
3 6 9 에서

6보다 작은 수는
1 2 3 (1의 배수 3개)
2 4 6 (2의 배수 3개)
3 6 9 (3의 배수 2개)

이런 식으로 개수를 얻을 수가 있다.

코드

n = int(input())
k = int(input())

start = 1
end = (n+1)**2

result=0
while start <=end:
    mid = (start+end)//2
    count=0
    for i in range(1,n+1):
        if (mid//i)<=n:
            count+=(mid//i)
        else:
            count+=n
    if count>=k: #count와 k가 무조건 일치하지 않는 경우도 있음
        result=mid
        end = mid-1
    else:
        start = mid+1

print(result)

if문을 사용해서 count를 더해주는 부분은 min()함수를 이용해서 더 간단하게 만들 수 있었다.

count+=min(mid//n=i,n)