프로그래머스 [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지(python)

문제URL : https://school.programmers.co.kr/learn/courses/30/lessons/340212

프로그래머스

 

문제 접근법 : 단순구현문제지만

숙련도를 최소값으로 설정해줘야하는 문제입니다.

그러나 1부터 시작하면 당연히 시간초과가 나올테고 또 적당한 큰값에서 시작해도 시간복잡도는 달라지지 않기때문에

적당한 값부터 시작해서 적당하게 줄여나가면서 탐색하는 

매개변수탐색 or 이분탐색 으로 쉽게 풀수있는문제입니다.

 

소스코드:

def solution(diffs, times, limit):
    answer = int(1e6)
    l,r= 1,int(1e6)
    while l<=r:
        mid = int((l+r)/2)
        total = 0
        for i in range(len(diffs)):
            if diffs[i]<=mid:
                total+=times[i]
            else:
                total+=(times[i]+times[i-1])*(diffs[i]-mid) +times[i]
        if total<=limit:
            answer = min(mid,answer)
            r=mid-1
        else:
            l= mid+1
    return answer

 

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.