문제 링크

https://programmers.co.kr/learn/courses/30/lessons/64062

문제 설명

• 디딤돌에 숫자들이 적혀있다
• 각 디딤돌은 지나갈 때마다 숫자가 1씩 줄어들고, 0이 되면 점프해서 지나가야 한다
• 점프할 수 있는 최대 거리 k가 주어진다
• 지나갈 수 있는 최대 사람 수 리턴

틀린 풀이

• DP
  • (i번째 값)과 (이후 k개의 값 중 최댓값)을 비교
  • i번째 값이 더 크면 종료
• 최댓값을 DP로 유지하는 게 어려웠다
• 그때그때 최댓값을 구하면 최악의 경우 O(N**2)이라 그런 것 같다
  • N은 stones의 길이 == 20만

맞은 풀이

• 이분 탐색
  • (start = 1, end = 2억) 으로 둬서 mid 명이 지나갔을 때
  • 남아있는 디딤돌 사이 거리가 k 이하이면
    • start = mid + 1
  • 아니면
    • end = mid
• N log M
  • N은 stones의 길이 == 20만
  • M은 디딤돌 숫자의 최댓값 == 2억

코드

def solution(stones, k):
    if len(stones) == 1:
        return stones[0]
    s = 1
    e = max(stones)
    while s < e:
        m = (s + e) // 2
        if possible(stones, k, m):
            s = m + 1
        else:
            e = m
    return s


def possible(stones, k, m):
    max_count = 0
    count = 0
    for i in range(len(stones)-1):
        if stones[i] - m <= 0:
            count += 1
            if stones[i+1] - m > 0:
                max_count = max(max_count, count)
                count = 0
    i += 1
    if stones[i] - m <= 0:
        count += 1
        max_count = max(max_count, count)
    if max_count >= k:
        return False
    return True