[Python] 백준 2110 & 백준 1238

import sys

n, c = map(int, sys.stdin.readline().split())
house = [int(sys.stdin.readline()) for _ in range(n)]

house.sort()

# 공유기 사이 거리 최솟값
start = 1
# 공유기 사이 거리 최댓값
end = house[n - 1] - house[0]
result = []

while start <= end:
    count = 1
    mid = (start + end) // 2 # mid 값을 공유기 사이 거리의 최솟값
    current = house[0]  # 공유기가 설치된 집의 위치
    for i in house:
        if current + mid <= i:  # 공유기 설치
            count += 1
            current = i
    if count >= c:  # mid 값에 따라 설치된 공유기의 개수가 c 보다 많거나 같으면
        start = mid + 1  # 거리를 늘린다.
        result.append(mid)
    else:
        end = mid - 1  # c 보다 작으면 거리를  줄인다.

print(max(result))

 

#백준 1238 파티

import sys
import heapq

n, m, k = map(int, input().split(' '))
graph = [[] for _ in range(n+1)]


for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append([b,c])

def dijkstra(start_node, end_node):
    queue = []
    heapq.heappush(queue, [0, start_node])
    min_distance = [1e9] * (n + 1) # 거리 초기화 중요!!
    min_distance[start_node] = 0
    while queue:
        [current_dist, current_node] = heapq.heappop(queue)
        if min_distance[current_node] < current_dist:
            continue
        min_distance[current_node] = current_dist
        for next_node, weight in graph[current_node]:
            cost = min_distance[current_node] + weight
            if cost < min_distance[next_node]:
                min_distance[next_node] = cost
                heapq.heappush(queue, [cost, next_node])
    return min_distance[end_node] # 반환값을 도착지까지 가는 *거리값*으로 설정

result = 0
for i in range(1, n+1):
    if i != k:
        result = max(result, dijkstra(i, k)+ dijkstra(k, i))

print(result)