[PCCP 기출문제] 2번 / 퍼즐 게임 챌린지

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

프로그래머스

음 일단 무식하게 ...

def solution(diffs, times, limit):
    level = 1
    while True:
        play_time = 0
        for i in range(len(diffs)):
            play_time += times[i] if diffs[i] <= level else (diffs[i] - level) * (times[i] + times[i - 1]) + times[i]
        if play_time <= limit:
            return level
        level += 1

시간제한에 걸려버린다. 이분 검색을 해야...

https://comdoc.tistory.com/entry/32-%EC%9D%B4%EC%A7%84-%EA%B2%80%EC%83%89Binary-Search

32. 이진 검색(Binary Search), 파이썬

def solution(diffs, times, limit):
    answer, left, right = 1, 1, 100_000
    while left <= right:
        level = (left + right) // 2
        if sum(times[i] if diffs[i] <= level else (diffs[i] - level) * (times[i] + times[i - 1]) + times[i]
               for i, _ in enumerate(diffs)) > limit:
            left = level + 1
        else:
            answer, right = level, level - 1
    return answer

테스트 1 〉	통과 (0.01ms, 10MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (0.01ms, 10MB)
테스트 4 〉	통과 (0.03ms, 10.4MB)
테스트 5 〉	통과 (0.03ms, 10.2MB)
테스트 6 〉	통과 (0.06ms, 10.2MB)
테스트 7 〉	통과 (0.03ms, 10.1MB)
테스트 8 〉	통과 (4.21ms, 10.2MB)
테스트 9 〉	통과 (4.59ms, 10.3MB)
테스트 10 〉	통과 (2.33ms, 10.4MB)
테스트 11 〉	통과 (3.68ms, 10.4MB)
테스트 12 〉	통과 (3.19ms, 10.3MB)
테스트 13 〉	통과 (3.58ms, 10.4MB)
테스트 14 〉	통과 (4.03ms, 10.4MB)
테스트 15 〉	통과 (1190.52ms, 35.1MB)
테스트 16 〉	통과 (1239.89ms, 34.7MB)
테스트 17 〉	통과 (710.46ms, 34.9MB)
테스트 18 〉	통과 (744.62ms, 34.7MB)
테스트 19 〉	통과 (1688.26ms, 34.1MB)
테스트 20 〉	통과 (881.53ms, 34.8MB)