[프로그래머스][KAKAO_인턴][2019] 징검다리 건너기

프로그래머스 코딩테스트 고득점 Kit의 문제입니다.

https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

코딩테스트 연습

 

문제

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

코딩테스트 연습 - 징검다리 건너기

 

내가 작성한 코드

def is_possible(stones, p, k):
    crnt_k = k
    for stone in stones:
        if stone - p < 0:
            crnt_k -= 1
            if crnt_k == 0:
                return False
        else:
            crnt_k = k
    return True


def solution(stones, k):
    answer = 0
    l, r = 1, 200_000_000

    while l != r:
        if r - l == 1:
            if is_possible(stones, r, k):
                return r
            return l

        mid = (r-l)//2 + l
        if is_possible(stones, mid, k):
            l = mid
        else:
            r = mid-1

    return l

• 파라메트릭 서치
  
  • 최적화 문제를 결정 문제로 변경
    - 최대 몇 명 건널 수 있는가? -> p명이 건널 수 있는가?

 

다른 사람이 작성한 코드

None

 

기억해야할 것

• 파라메트릭 서치를 이전에 본 적 있어서 쉽게 접근했다