[백준2110] 공유기 설치

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

 

 

문제 해결 방법

 

0. 카운트 변수를 생성한다 초기값은 0

1. 받은 활호문장을 순회하면서 현재 괄호를 열고있는게 몇개인지 계속 체크를 한다. 

2. 괄호를 닫게 될 경우가 2가지 가 있다. 

    2-1. 순회하면서 닫는 괄호가 나온 경우, 직전에 여는 괄호가 나왔는지 체크한다. 이것은 괄호를 순회하며 사전에 flag로 지속적으로 체크한다. (flag=1)

    2-2. 순회하면서 닫는 괄호가 나온 경우, 직전에 여는 괄호가 나오지 않은 경우, flag는 0인 경우이다. 

 

3. 2-1의 조건을 통과한 경우, 현재 열고있는 괄호의 갯수만큼 카운트 변수에 더해준다. 

    2-2의 조건을 통과한 경우, 

 

 

코드 구현

정답 코드 

import sys
input = sys.stdin.readline

n, c = map(int, input().split())

tmp=[]
for i in range(n):
    x = int(input())
    tmp.append(x)

tmp.sort()
print(tmp)

start = 1 # 최소 거리
end = tmp[-1]-tmp[0] # 최대 거리
cnt=1
result = 0
while start<=end:
    mid = (start + end) // 2 # 중간 간격 거리
    cnt = 1 # 첫번째 원소는 이미 방문한 것으로 침
    curr = tmp[0]

    for i in range(1, len(tmp)):
        if tmp[i] >= mid + curr: # 이동하려는 간격이 (중간간격 거리 + 현재 위치) 보다 크면
            cnt+=1
            curr=tmp[i]
        
    if cnt >= c: # 공유기 설치가 끝났으면, 범위를 좀 더 퍼트려줄 필요가 있다. 
        start=mid+1
        result=mid
    else: # 범위에 못미치면 범위를 줄여줄 필요가 있다. 
        end=mid-1

print(result)

 

 

시간/공간 복잡도

n^2으로 못풂

 

최적화 및 개선

• 따로 하지않음

 

어려웠던 점

• 상당히 낯설고 어렵게 느껴지는 문제이다. 
• 이분탐색 알고리즘을 적용하고 싶은데 와닿는 이해가 되지 않는 문제였다. => 다음에 다시 풀어볼 문제

 

알게된 것

• 이분탐색을 이렇게도 사용할 수 있다는점 
• 이진탐색을 공유기 사이에 거리에 써야하는 것
•