[백준 6209번] 제자리 멀리뛰기 문제 풀이

 
< 문제 >

 
 
 
< 입출력 >

 
 
 
< TRY 1 > - 시간초과
 
: 거리 배열을 구해, m번만큼 최솟값이 최대값이 되는 값을 거리배열로 바꿈
 이때, 최대값 여부를 확인하는 과정에서 처음부터 배열의 크기를 모두 돌아 비교하니 시간초과가 났다.
 

d, n, m = map(int, input().split())
where = []
for i in range(n):
    where.append(int(input()))

where.sort()
distance = []

distance.append(where[0])
for i in range(n-1):
    distance.append(where[i+1]-where[i])

distance.append(d - where[n-1])

for i in range(m):
    remove_index = 0
    min_num = 0
    for j in range(0, len(distance)-1):
        new_arr = []

        for k in distance[:j]:
            new_arr.append(k)
        new_arr.append(distance[j] + distance[j+1])
        for k in distance[j+2:len(distance)]:
            new_arr.append(k)
        if min_num < min(new_arr):
            remove_index = j
            min_num = min(new_arr)
    new_distance = []
    for k in distance[0:remove_index]:
        new_distance.append(k)
    new_distance.append(distance[remove_index] + distance[remove_index + 1])
    for k in distance[remove_index + 2:len(distance)]:
        new_distance.append(k)
    distance = new_distance

print(min(distance))

 
 
 
 
< TRY 2 >
: for문을 3번 중첩한 것이 문제인 듯 하나, 새로운 배열을 만들어 비교하는 것 외에는 해결 방법이 도무지 떠오르지 않는다.... 소스 코드를 참고해보니, 놀랍게도 이진 탐색으로 푼다.
 

d, n, m = map(int, input().split())
where = []
for i in range(n):
    where.append(int(input()))

where.sort()
start = 0
end = d
dist = 0
while start <= end:
    mid = (start + end) // 2
    count = 0 
    now = 0
    min_distance = d
    for x in where:
        if x - now >= mid:
            min_distance = min(min_distance, x - now)
            now = x
        else:
            count += 1

    min_distance = min(min_distance, d - now)

    if count > m:
        end = mid - 1
    else:
        dist = max(dist, min_distance)
        start = mid + 1

print(dist)