[파이썬(python)] 이것이 취업을 위한 코딩테스트다 떡볶이 떡 만들기 이진탐색

처음에는 순차탐색을 이용했다. 이진탐색을 구현할 생각은 못했는데, 탐색 범위가 1에서 10억까지인걸 보니 이진탐색으로 구현해야 효율적으로 코드를 구성할수 있다.

 

그래서 답지를 보고 참고한 코드

 

n, m = map(int, input().split()) #떡 개수와 필요한 떡 길이 입력받기
rice = list(map(int, input().split())) #떡 길이 배열 생성

start = 0
end = max(rice)

result = 0

#이진 탐색 수행
while(start <= end):
    total = 0
    mid = (start + end) // 2
    
    for x in rice:
        if x > mid: #총 떡의 양 계산
            total += x - mid

    if total < m: #떡의 양이 부족하면 더 많이자르기. 왼쪽 부분 탐색
        end = mid - 1
    else: #떡의 양이 충분하면 덜 자르기. 오른쪽 부분 탐색
        result = mid
        start = mid + 1

print(result)

 

 

A 29 공유기 설치

 

이 문제 또한 이진 탐색이다. 이진 탐색을 이용한다는 것은 알았으나, 두 공유기 사이의 거리 최소값을 start로,

최대값을 end로 설정한 뒤

start와 end 사이의 중간값을 gap으로 설정, 

해당 gap을 만족하는 공유기 값을 세면서 이진탐색을 적용하는 아이디어를 떠올리지 못했다.

start를 가장 왼쪽의 공유기, end를 가장 오른쪽의 공유기로 설정하는 아이디어를 생각했으나 ..

뭔가 구현이 너무 어려워서 포기했다.

 

소스코드

 

import sys
n, c = map(int, sys.stdin.readline().split())

#집의 개수와 공유기의 개수 입력
home = []

#집의 위치 입력받기
for _ in range(n):
    home.append(int(sys.stdin.readline()))

home.sort()

start = 1 #공유기 거리의 최소값은 늘 1
end = home[-1] - home[0] # 공유기 거리의 최대값. 
result = 0

while start <= end:
    gap = (start + end)// 2 #중간값으로 gap 설정
    count = 1 #home[0]에 설치하므로 count는 1부터 시작
    install = 0 #0에 설치
    
    for i in range(n): #공유기 설치
        if home[i] - home[install] >= gap:

#이미 설치된 install 과 i 사이의 거리가 gap보다 크면 설치. 
            install = i
            count += 1

    if count < c:

#설치 불가능. gap 줄여야함. end를 gap-1로 설정
        end = gap-1
        continue

    else:

#설치 가능. gap의 값을 저장해둔 뒤 gap이 증가해도 설치가 가능한지 확인해야함
        start = gap + 1
        result = gap


print(result)