프로그래머스 [Lv. 2] [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지 {언어 : Python}

문제 링크

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

프로그래머스

정답 코드

def solution(diffs, times, limit):
    lenDT = len(diffs)
    
    # 이분 탐색
    minLev = 1
    maxLev = 100000
    while minLev <= maxLev:
        level = (minLev+maxLev) // 2
        currentTimes = times[0]
        # 소요 시간 계산
        for i in range(1, lenDT):
            if currentTimes > limit:
                break
            diff = diffs[i]
            time = times[i]
            prevTime = times[i-1]
            if level >= diff:
                currentTimes += time
            else:
                currentTimes += (prevTime+time) * (diff-level) + time
        
        # 범위 재조정
        if currentTimes > limit:
            minLev = level + 1
        else:
            maxLev = level - 1
    
    answer = minLev
    return answer

풀이 방법

1. 문제를 제한 시간안에 다 풀 수 있는 수준을 찾는 문제로 이진 탐색을 바로 떠올려야 한다.
2. 범위를 좁혀가면서 정답을 찾는다.
   1. 현재 레벨이 문제를 다 풀 수 있다면
      1. 현재 레벨보다 작았을 때도 문제를 풀 수 있는지 확인이 필요하므로 maxLev을 level - 1로 줄여줌으로써 범위를 좁힐 수 있다.
   2. 현재 레벨로는 문제를 제한 시간 내에 다 풀 수 없다면
      1. 현재 레벨 자체를 올려야 하므로 minLev을 level + 1로 올려줌으로써 범위를 좁힐 수 있다.
3. 결과적으로 while이 종료되면 minLev과 maxLev은 같아지면서 둘 중 아무거나 반환하면 끝!

느낀점

• 이제는 바로 이진탐색이 떠오르는 수준에 올랐지만 방심하면 안된다.