[프로그래머스] 징검다리 건너기 - Python

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

프로그래머스

---

• 풀이
  • 1명씩 뛰면 시간초과 100%
  • i번째 돌을 밟을 수 있는지 체크 + 밟을 수 있다면 몇개 건너뛰고 밟았는지도 알아야함
    • 탐색범위가 매우크다
      • 이진 탐색!!!!!
  • 만약 돌이 [5,5,3,5]이고 k가 2명 5명이 건널 수 있다.
    • 최소 건널 수 있는 사람 수는 1 
    • 최대 건널 수 있는 사람 수는  max(stones) 
  • mid명이 건넌 후 mid+1번째 사람이 건널 수 있는지 확인
    • 건널 수 있으면 사람을 늘려보자 + (mid+1)값 저장

• 코드

def solution(stones, k):
    answer = 0
    s = 1
    # 최대 밟을 수 있는 횟수
    e = max(stones)
    while s <= e:
        # mid명이 건넌 후 다음 사람이 건널 수 있는가?
        mid = (s+e)//2
        # 몇칸씩 건너는지
        l = []
        cnt = 1
        for i in range(len(stones)):
        	# mid명이 건넜으니 
            # 밟을 수 없는 돌 -> 건너뛰기
            if mid >= stones[i]:
                cnt += 1
            # 밟을 수 있는 돌 -> 몇개 건너뛰었는지 저장
            else:
                l.append(cnt)
                cnt = 1
        # 마지막 건너뛰기
        l.append(cnt)
        # 건너뛸 수 있는 최대보다 크면 다 못 건넌다... -> 사람 줄이자
        if max(l) > k:
            e = mid - 1
        # 다 건널 수 있다 -> 사람 늘려보자 + (mid+1)값 저장
        else:
            s = mid + 1
            answer = mid+1
    return answer