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

0. 사용언어 : Python

1. 문제

 

2. 문제 분석

2-1. 문제

• 각 퍼즐에는 난이도(diff)와 소요 시간(time)이 있으며, 숙련도(level)에 따라 퍼즐을 푸는 데 걸리는 시간이 달라진다.
• 규칙 설명:
  - 현재 퍼즐의 난이도가 숙련도 이하일 경우(diff <= level), 퍼즐을 틀리지 않고 해당 퍼즐의 소요 시간(time_cur)만큼의 시간을 사용하여 해결할 수 있다
  - 현재 퍼즐의 난이도가 숙련도보다 높을 경우(diff > level), 퍼즐을 여러 번 틀리게 된다
  - 이때 틀리는 횟수는 diff - level 이다.
  - 퍼즐을 틀릴 때마다, 퍼즐의 소요 시간(time_cur)과 이전 퍼즐의 소요 시간(time_prev)이 더해진 시간을 추가로 사용한다.
  - 마지막으로 틀리지 않고 퍼즐을 풀 때는 소요 시간(time_cur)만 더한다.

 

2-2. 제한사항

• 퍼즐의 개수(n):
  최대 300,000개의 퍼즐이 주어질 수 있다
  따라서 모든 퍼즐에 대해 단순히 반복 계산을 수행하면 시간 초과가 발생할 수 있다
  -> 이진 탐색 필요
  
  
• 난이도(diffs[i])와 소요 시간(times[i]):
  각 퍼즐의 난이도는 1 <= diffs[i] <= 100,000 범위이다
  각 퍼즐의 소요 시간은 1 <= times[i] <= 10,000 범위이다.
  첫 번째 퍼즐의 난이도는 항상 1(diffs[0] = 1로 주어지므로, 첫 번째 퍼즐에서 실패하는 경우는 없다
  
  
• 제한 시간(limit):
  limit의 최대값은 10^15로 매우 큰 수이다.
  따라서, 모든 계산을 수행한 후 매번 limit과 비교하여 초과 여부를 빠르게 확인해야 한다.
  
  
• 숙련도(level) 범위:
  최소값은 1로 고정이다. 숙련도는 음수가 될 수 없기 때문에 level >= 1 이다.
  최대값은 max(diffs) 이다. level이 max(diffs)이상이면 모든 퍼즐의 난이도보다 높으므로 무조건 한 번에 풀 수 있다.

2-3. 핵심

이진 탐색을 사용하여 level 범위를 줄여나가며 제한 시간을 만족하는 최소값을 찾는다.

 

3. 문제 풀이

def solution(diffs, times, limit):
    # 주어진 숙련도 level로 퍼즐을 제한 시간 내에 모두 풀 수 있는지 확인하는 함수
    def can_complete_in_time(level):
        total_time = 0  # 퍼즐을 푸는 데 걸린 총 시간

        for i in range(len(diffs)):
            diff, time_cur = diffs[i], times[i]
            time_prev = times[i - 1] if i > 0 else 0  # 첫 퍼즐은 이전 시간이 없음

            if diff <= level:
                # 한 번에 풀 수 있는 경우
                total_time += time_cur
            else:
                # 여러 번 틀리는 경우
                fails = diff - level  # 몇 번 틀리는지 계산
                total_time += fails * (time_cur + time_prev) + time_cur

            # 제한 시간을 초과하면 False 반환
            if total_time > limit:
                return False

        return total_time <= limit  # 제한 시간 내에 모든 퍼즐을 풀었는지 확인

    # 이진 탐색 범위 설정
    left, right = 1, max(diffs)
    answer = right  # 최대값으로 초기화

    while left <= right:
        mid = (left + right) // 2  # 현재 탐색 중간 값
        if can_complete_in_time(mid):
            answer = mid  # 현재 level로 제한 시간을 만족한다면 답으로 저장
            right = mid - 1  # 더 낮은 level을 찾기 위해 범위를 줄임
        else:
            left = mid + 1  # 현재 level로 제한 시간을 만족하지 못하면 level을 높임

    return answer

 

solution 함수는 diffs, times, limit 을 매개변수로 받는다

• diffs: 퍼즐 난이도 리스트
• times: 퍼즐마다의 소요 시간 리스트
• limit: 모든 퍼즐을 해결할 수 있는 최대 제한 시간

def can_complete_in_time(level):

• 내부 함수 can_complete_in_time(level) 을 정의한다.
• 주어진 level로 제한 시간 내에 모든 퍼즐을 해결할 수 있는지 확인한다.

total_time = 0

• total_time 변수를 초기화한다. 이 변수는 level 로 퍼즐을 풀 때 총 걸리는 시간이 저장된다.

for i in range(len(diffs)):
    diff, time_cur = diffs[i], times[i]
    time_prev = times[i - 1] if i > 0 else 0

• diffs 리스트의 모든 요소를 순회한다.
• 현재 퍼즐의 난이도 diff 와 소요 시간 time_cur 을 각각 diffs[i] 와 times[i] 에서 가져온다
• time_prev 는 이전 퍼즐의 소요 시간을 의미한다.
  첫 번째 퍼즐(i == 0)인 경우 time_prev는 0으로 설정한다.
  이후 퍼즐에서는 times[i - 1]로 설정하여, 이전 퍼즐의 소요 시간을 가져온다.

if diff <= level:
    total_time += time_cur
else:
    fails = diff - level
    total_time += fail * (time_cur + time_prev) + time_cur

• 현재 level 이 diff 보다 크거나 같다면 한 번에 퍼즐을 풀 수 있다
• 이때, total_time 에 time_cur (현재 퍼즐 소요 시간)만 더해준다.
• level 이 diff 보다 작을 경우, 퍼즐을 틀리게 된다.
  fails = diff - level 은 퍼즐을 틀리는 횟수를 계산한다.
  각 실패마다 time_cur + time_prev 의 시간이 소요되며, 실패 후 다시 풀 때는 time_cur 만 추가로 소요된다.
• fails * (time_cur + time_prev) + time_cur 을 total_time 에 더해준다.

if total_time > limit:
    return False

• total_time 이 limit 을 초과하는 순간, 더 이상 조건을 만족할 수 없으므로 False 를 반환하여 함수를 종료한다.

return total_time <= limit

• 모든 퍼즐을 제한 시간 내에 해결할 수 있다면 True 를 반환한다.

---

이진 탐색

left, right = 1, max(diffs)
answer = right

• left 와 right 변수는 이진 탐색의 범위를 나타낸다
  left = 1 로 최소 level 을 설정한다.
  right = max(diffs) 로 최대 level 을 설정한다. level 이 max(diffs) 이상이면 모든 퍼즐을 해결할 수 있기 때문이다
• answer 는 가능한 최소 level 을 저장하기 위한 변수로, right 값으로 초기화한다.

while left <= right:
    mid = (left + right)
    if can_complete_in_time(mid):
        answer = mid
        right = mid - 1
    else:
        left = mid + 1

• left 가 right 보다 작거나 같을 때까지 반복한다.
• mid 는 현재 탐색 범위의 중간 값으로, 현재 시도할 level 값이다.
• can_complete_in_time(mid) 가 True 를 반환하면, mid 수준의 level 로 제한 시간 내에 모든 퍼즐을 해결할 수 있다는 뜻이다.
• 이때, answer 를 mid 로 업데이트하고 더 낮은 level 에서도 가능할지 확인하기 위해 right = mid - 1 로 범위를 줄인다.
• can_complete_in_time(mid) 가 False 를 반환하면, mid 수준의 level 로는 모든 퍼즐을 제한 시간내에 해결할 수 없다는 뜻이다.
• 따라서 더 높은 level이 필요하므로, left 를 mid + 1 로 설정하여 탐색 범위를 높인다.

return answer

• 이진 탐색이 끝나면 answer 에 가능한 최소 숙련도(level)가 저장되어 있다.
• 이 값을 반환하면 끝!