[프로그래머스/파이썬] PCCP 기출문제 2번 퍼즐 게임 챌린지 - 이분탐색

시간복잡도 때문에 이분탐색을 써야 한다는 건 금방 알아차릴 수 있었다.

(사실 아는 알고리즘이 몇개 없음 ㅎㅎ)

그런데 테스트케이스 14번만 통과를 못하는...

항상 반례 찾는게 미션인듯하다.

 

도통 모르겠어서 질문하기를 들어갔는데 이미 나와 같은 선배님들이 몇몇 있었고,

퍼즐 게임 챌린지 테스트 케이스 14번 반례는 마지막에 적어놓았다.

 

[프로그래머스 PCCP 퍼즐 게임 챌린지 링크]

↓  ↓  ↓

프로그래머스

 

 

문제

 

당신은 순서대로 n개의 퍼즐을 제한 시간 내에 풀어야 하는 퍼즐 게임을 하고 있습니다. 각 퍼즐은 난이도와 소요 시간이 정해져 있습니다. 당신의 숙련도에 따라 퍼즐을 풀 때 틀리는 횟수가 바뀌게 됩니다. 현재 퍼즐의 난이도를 diff, 현재 퍼즐의 소요 시간을 time_cur, 이전 퍼즐의 소요 시간을 time_prev, 당신의 숙련도를 level이라 하면, 게임은 다음과 같이 진행됩니다.

• diff ≤ level이면 퍼즐을 틀리지 않고 time_cur만큼의 시간을 사용하여 해결합니다.
• diff > level이면, 퍼즐을 총 diff - level번 틀립니다. 퍼즐을 틀릴 때마다, time_cur만큼의 시간을 사용하며, 추가로 time_prev만큼의 시간을 사용해 이전 퍼즐을 다시 풀고 와야 합니다. 이전 퍼즐을 다시 풀 때는 이전 퍼즐의 난이도에 상관없이 틀리지 않습니다. diff - level번 틀린 이후에 다시 퍼즐을 풀면 time_cur만큼의 시간을 사용하여 퍼즐을 해결합니다.

예를 들어 diff = 3, time_cur = 2, time_prev = 4인 경우, level에 따라 퍼즐을 푸는 데 걸리는 시간은 다음과 같습니다.

• level = 1이면, 퍼즐을 3 - 1 = 2번 틀립니다. 한 번 틀릴 때마다 2 + 4 = 6의 시간을 사용하고, 다시 퍼즐을 푸는 데 2의 시간을 사용하므로 총 6 × 2 + 2 = 14의 시간을 사용하게 됩니다.
• level = 2이면, 퍼즐을 3 - 2 = 1번 틀리므로, 6 + 2 = 8의 시간을 사용하게 됩니다.
• level ≥ 3이면 퍼즐을 틀리지 않으며, 2의 시간을 사용하게 됩니다.

퍼즐 게임에는 전체 제한 시간 limit가 정해져 있습니다. 제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 구하려고 합니다. 난이도, 소요 시간은 모두 양의 정수며, 숙련도도 양의 정수여야 합니다.

퍼즐의 난이도를 순서대로 담은 1차원 정수 배열 diffs, 퍼즐의 소요 시간을 순서대로 담은 1차원 정수 배열 times, 전체 제한 시간 limit이 매개변수로 주어집니다. 제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 정수로 return 하도록 solution 함수를 완성해 주세요.

 

 

풀이

 

숙련도 level은 diffs의 최대값보다 작거나 같기 때문에 max(diffs)로 초기화했다.

총 소요시간이 제한 시간보다 크면 답이 될 수 없고 level은 지금보다 크기 때문에 이분탐색의 start를 +1 해준다.

제한 시간보다 작으면 답이 될 수도 있으니 answer에 저장해 주고 end를 -1 한 후 다시 탐색한다.

 

testcase 14번의 반례 해결)

diffs=[1,1], times=[1,2], limit=50인 경우 답은 1인데 0이 리턴되었다.

처음 코드는 start 초기값을 0으로 줬는데 1로 바꿔서 해결했다.

 

코드

 

def solution(diffs, times, limit):
    end = max(diffs)
    start = 1
    level = end
    answer = end
    sum_time = 0

    while start <= end:
        for i, data in enumerate(zip(diffs, times)):	# 총 소요시간 계산
            diff, time = data
            if diff <= level:
                sum_time += time
            else:
                sum_time += (time+times[i-1])*(diff-level)+time
        else:		# 이분 탐색
            if sum_time > limit:
                start = level+1
            else:
                answer = level
                end = level-1
            level = (start+end)//2
            sum_time = 0
    return answer