[백준] 1477 : 휴게소 세우기

문제링크

풀이

import math
import sys

input = sys.stdin.readline
n, m, l = map(int, input().split())
분기점 = [0] + list(map(int, input().split())) + [l]
분기점.sort()

for i in range(m):
  구간길이 = [분기점[i+1] - 분기점[i] for i in range(n+1)]

몇등분 = [1] * len(구간길이)

for _ in range(m):
  등분된길이 = [math.ceil(x / y) for x,y in zip(구간길이, 몇등분)]
  더나눌구간 = 등분된길이.index(max(등분된길이))
  몇등분[더나눌구간] += 1
  
최대구간길이 = max([math.ceil(x / y) for x,y in zip(구간길이, 몇등분)])
print(최대구간길이)

풀이방법

1. 각 구간길이와 각 구간길이를 몇등분할지 저장하는 배열을 선언한다.
2. m번의 시행마다 구간길이 / 몇등분을 반올림한 결과가 가장 큰 인덱스의 등분을 +1 증가시킨다.
3. 최종적으로 구간길이 / 몇등분 을 반올림한 결과가 가장 큰 값이 휴게소간 최대거리가 가장 짧은때의 값이된다.

채점결과