[프로그래머스] 징검다리

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43236#

프로그래머스

 

이전에 풀었던 '징검다리 건너기' 문제와는 비슷하면서도 살짝 다른 문제이다.

 

---

 

주요 아이디어

1. 목표값인  "각 지점 사이 거리의 최소값 중에서 가장 큰 값" 을 이분탐색 대상으로 가진다.

이게 말이 조금 헷갈리는데,

n개 이하의 바위를 파괴하는 모든 경우의 수에서

max (min(x1, x2 파괴 시), min(x2, x3 파괴 시) ...) 를 의미한다.

그림으로 설명

그럼 모든 n개의 돌을 파괴해서 최소값 비교하면 안되나??

당연히 이분탐색 문제기때문에 시간복잡도에서 걸린다.

 

 

2. 문제와 그림을 다시 살펴보면, 거리의 최소값을 구하는 것이기에 그보다 큰 간격은 정답과 아무 상관이 없다.

 

다시 원점으로 돌아가보자. 우리가 구해야 하는 것은? 

 "각 지점 사이 거리의 최소값 중에서 가장 큰 값" 그 자체이다.

그렇기 때문에,  "각 지점 사이 거리의 최소값 중에서 가장 큰 값" 을 구하기 위해서 탐색하고 있는 mid 값과 비교를 하며 mid 보다 간격이 작은 바위들을 제거하면 된다.

바위가 제거될수록 최소값은 같거나 늘어나기 때문에, 제거된 바위가 n개 이하일 경우 기준 거리 (=mid) 를 늘리고

제거된 바위가 n개 초과할 경우 너무 많은 바위를 제거한 것이므로 기준 거리를 좁히면 된다.

 

 

3. 여기서 중요한 점!

바로 끝점까지 도달하는 것이기 때문에 rocks에다가 끝점 포인트인 distance를 추가해주어야 한다는 것이다.

(이거 빼먹어서 2번 틀렸다...)

 

---

 

코드 구현 (Python 3)

def solution(distance, rocks, n):
    start, end = 0, distance
    answer = 0 # 최소값 중 가장 큰 값
    
    # 정렬 먼저!
    rocks.append(distance) # 최대거리 추가때문에 일부 테스트에서 실패한듯
    rocks.sort()
    
    while start <= end:
        # 간격!! 중간값 - 12부터 시작
        mid = (start + end) // 2
        # 중간값보다 간격 작은 바위 제거
        removed_rocks = 0
        prev_rock = 0
        
        for rock in rocks:
            if rock - prev_rock < mid:
                removed_rocks += 1
            else:
                prev_rock = rock
        
        # 제거된 바위가 n 이하일 경우, 더 큰 최소값을 바랄 수 있음
        # 바위가 제거될수록 거리는 무조건 늘어나기 때문!
        if removed_rocks <= n:
            start = mid + 1
            answer = mid
        
        # 아닐 경우, 값이 더 낮아야 바위를 n보다 적게 제거 -> end를 현재 위치로 다시 갱신
        else:
            end = mid - 1
    
    return answer

 

 

 

---

 

제출 결과

 

 

---

유사 문제

공유기 설치 : https://www.acmicpc.net/problem/2110

랜선 자르기 : https://www.acmicpc.net/problem/1654

나무 자르기 : https://www.acmicpc.net/problem/2805