[프로그래머스/LV2] 퍼즐 문제

problem : https://school.programmers.co.kr/learn/courses/30/lessons/340212?language=python3

프로그래머스

difficulty : LV2

status : solved

---

모바일로 간략하게 써본다! (나중에 수정 예정이다)

우선 확인해야 할 사항은, 주어진 level에서 총 소요시간이 얼마나 소요되는지를 구현하는 제 1과제이다. 수식으로 결론을 지으면 다음과 같이 나온다.

t_cur_total = t_cur + (t_cur + t_prev) * max(0, diff_cur - level)

수식 유도 자체는 그리 어렵지 않을 것이고, 문제 예제에 바로 수식을 활용한 풀이를 보여 주니 그대로 구현만 해 주면 되겠다.

두 번째는 이 수식을 어떻게 효율적으로 적용할지에 대한 문제가 된다. 최대 diff는 100000이고, diff의 길이는 최대 300000이므로 이걸 모두 테스트해볼 순 없는 노릇이다.

이분 탐색을 이용하면 이 시간복잡도를 O(logN)으로 줄일 수 있다. 통과할 수 있는 최소 level을 찾는 문제는 lower bound를 찾는 문제로 변한다.

def check(diffs, times, limit, level) :
    prev = 0
    total = 0
    for d, t in zip(diffs, times) :   
        total += t+(t+prev)*max(0, d - level)
        if total > limit :
            return False
        prev = t
    return True
            
def solution(diffs, times, limit):
    start, end = 1, max(diffs)
    while start < end :
        mid = (start+end)//2
        if check(diffs, times, limit, mid):
            end = mid
        else :
            start = mid+1
    return end

p.s. 모바일로 문제를 푸는 건 색다른 경험이다!