[Programmers] Level 2. 퍼즐 게임

🔗 Problem Link

프로그래머스

---

❔Thinking

• 난이도(diffs)와 풀이시간(times)이 정해진 퍼즐을 모두 해결할 수 있는 숙련도(level)의 최솟값을 찾아야 한다.
• 현재의 숙련도보다 어려운 퍼즐일 경우, 총 풀이시간에 현재 풀이시간과 이전 풀이시간을 난이도-숙련도 만큼 곱한다.

---

💻Solution

def solution(diffs, times, limit):
    n = len(diffs)
    left, right = 1, max(diffs)
    while left < right:
        tmp_time = 0
        level = (left+right) // 2
        for i in range(n):
            if level >= diffs[i]:
                tmp_time += times[i]
            else:
                tmp_time += (times[i]+times[i-1])*(diffs[i]-level) + times[i]
        if tmp_time == limit:
            right = level
            break
        elif tmp_time >= limit:
            left = level+1
        else:
            right = level
    return right

---

🗝️keypoint

1. 일정한 조건과 범위 내에서의 최솟값을 찾는 경우, 이분 탐색을 떠올린다.
2. limit과 정확히 일치하는 level의 경우가 아니라면, left <= right 조건 시 무한루프에 빠질 수 있다.