[문제 풀이] 10월 30일

 

< 나무 자르기 > - 백준 2805

 

1. 시간 초과

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
trees = list(map(int, input().split()))

start = max(trees)
while start > 0:
    sums = 0
    start -= 1
    for tree in trees:
        if int(tree) > start:
            len = int(tree) - start
            sums += len
    if sums >= m:
        print(start)
        break

 

2. 정답 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
trees = list(map(int, input().split()))
start, end = 1, max(trees)

while start <= end:
    mid = (start + end) // 2
    sums = 0
    for tree in trees:
        if tree > mid:
            sums += (tree - mid)
    if sums >= m:
        start = mid + 1
    else:
        end = mid - 1
print(end)

 

 

 

< 수 찾기 > - 백준 1920

import sys
input = sys.stdin.readline

n = int(input())
n_nums = list(map(int, input().split()))
n_nums.sort()
m = int(input())
m_nums = list(map(int, input().split()))

for num in m_nums:
    start = 0
    end = n - 1
    inlist = False
    while start <= end:
        mid = (start + end) // 2
        if num == n_nums[mid]:
            inlist = True
            print(1)
            break
        elif num < n_nums[mid]:
            end = mid - 1
        elif num > n_nums[mid]:
            start = mid + 1
    if inlist == False:
        print(0)

 

 

 

< 공유기 설치 > - 백준 2110

 

- 공유기 개수 조건을 어떻게 생각해내지,,,

- 이해하는 데 오래 걸렸다

 

import sys
input = sys.stdin.readline

n, c = map(int,input().split())
houses = [int(input()) for i in range(n)]
houses.sort()  # [1, 2, 4, 8, 9]
start = 1  # 집 사이의 최소 거리
end = houses[n-1] - houses[0]  # 집 사이의 최대 거리
result = 0

if c == 2:
    print(houses[n-1] - houses[0])
else:
    while start <= end:
        mid = (start + end) //2
        count = 1
        cur = houses[0]
        for house in houses:  # 공유기 설치 몇개 가능한가
            if house - cur >= mid:
                count += 1
                cur = house
        if count >= c:  # 설치 가능한 공유기 수가 c보다 크면 거리를 늘려야 하고
            result = mid
            start = mid + 1
        elif count < c:  # 설치 가능한 공유기 수가 c보다 작으면 거리를 좁혀야 함
            end = mid - 1
    print(result)