문제 요약
퍼즐을 순서대로 풀어야 합니다.
각 퍼즐에는 난이도 diffs[i]와 소요 시간 times[i]가 있습니다. 플레이어의 숙련도를 level이라고 할 때, 퍼즐을 푸는 규칙은 다음과 같습니다.
diffs[i] <= level이면 틀리지 않고times[i]만 사용해 해결합니다.diffs[i] > level이면diffs[i] - level번 틀립니다.- 한 번 틀릴 때마다 현재 퍼즐 시간
times[i]와 이전 퍼즐 시간times[i - 1]을 함께 사용합니다. - 마지막으로 현재 퍼즐을 한 번 더 풀어 해결하므로
times[i]가 추가됩니다.
즉, diffs[i] > level일 때 i번째 퍼즐에 걸리는 시간은 다음과 같습니다.
(times[i] + times[i - 1]) × (diffs[i] - level) + times[i]모든 퍼즐을 제한 시간 limit 안에 풀 수 있는 최소 숙련도를 구해야 합니다.
핵심 아이디어
숙련도 level이 높아질수록 틀리는 횟수는 줄어듭니다.
따라서 총 소요 시간은 숙련도가 높아질수록 감소하거나 그대로입니다.
level 증가
→ 틀리는 횟수 감소
→ 총 소요 시간 감소 또는 유지즉, 어떤 숙련도 x로 제한 시간 안에 모든 퍼즐을 풀 수 있다면, x보다 큰 숙련도로도 당연히 풀 수 있습니다.
이런 구조를 단조성이라고 하며, 최소로 가능한 숙련도를 찾는 데 이분 탐색을 사용할 수 있습니다.
판정 함수
먼저 특정 숙련도 level로 모든 퍼즐을 제한 시간 안에 풀 수 있는지 확인하는 함수를 만듭니다.
def can_clear(level):
total = 0
for i in range(len(diffs)):
if diffs[i] <= level:
total += times[i]
else:
mistake = diffs[i] - level
total += (times[i] + times[i - 1]) * mistake + times[i]
if total > limit:
return False
return True총 시간이 limit을 넘는 순간 더 계산할 필요가 없으므로 바로 False를 반환합니다.
이렇게 하면 큰 입력에서도 불필요한 계산을 줄일 수 있습니다.
이분 탐색 범위
숙련도의 최솟값은 1입니다.
숙련도가 모든 퍼즐의 난이도 이상이면 어떤 퍼즐도 틀리지 않습니다. 따라서 탐색의 오른쪽 끝은 max(diffs)로 둘 수 있습니다.
left = 1
right = max(diffs)이제 mid 숙련도로 제한 시간 안에 풀 수 있는지 확인합니다.
- 가능하다면 더 작은 숙련도를 찾아봅니다.
- 불가능하다면 숙련도를 높여야 합니다.
Python 풀이
def solution(diffs, times, limit):
n = len(diffs)
def can_clear(level):
total = 0
for i in range(n):
if diffs[i] <= level:
total += times[i]
else:
mistake = diffs[i] - level
total += (times[i] + times[i - 1]) * mistake + times[i]
if total > limit:
return False
return True
left = 1
right = max(diffs)
answer = right
while left <= right:
mid = (left + right) // 2
if can_clear(mid):
answer = mid
right = mid - 1
else:
left = mid + 1
return answer예제 분석
다음과 같은 입력을 생각해 보겠습니다.
diffs = [1, 4, 4, 2]
times = [6, 3, 8, 2]
limit = 59숙련도가 2인 경우를 계산하면 다음과 같습니다.
1번째 퍼즐
diff = 1, level = 2난이도가 숙련도 이하이므로 틀리지 않습니다.
소요 시간 = 62번째 퍼즐
diff = 4, level = 24 - 2 = 2번 틀립니다.
(3 + 6) × 2 + 3 = 213번째 퍼즐
diff = 4, level = 24 - 2 = 2번 틀립니다.
(8 + 3) × 2 + 8 = 304번째 퍼즐
diff = 2, level = 2난이도가 숙련도 이하이므로 틀리지 않습니다.
소요 시간 = 2총 시간은 다음과 같습니다.
6 + 21 + 30 + 2 = 59제한 시간 안에 모든 퍼즐을 풀 수 있습니다.
숙련도가 2보다 작으면 제한 시간 안에 풀 수 없으므로 정답은 2입니다.
큰 수 예제
diffs = [1, 99999, 100000, 99995]
times = [9999, 9001, 9999, 9001]
limit = 3456789012정답은 39354입니다.
숙련도가 39354일 때 총 소요 시간은 다음과 같습니다.
1번째 퍼즐: 9999
2번째 퍼즐: (9001 + 9999) × 60645 + 9001 = 1152264001
3번째 퍼즐: (9999 + 9001) × 60646 + 9999 = 1152283999
4번째 퍼즐: (9001 + 9999) × 60641 + 9001 = 1152188001총합은 다음과 같습니다.
9999 + 1152264001 + 1152283999 + 1152188001 = 3456746000제한 시간 3456789012 안에 해결할 수 있습니다.
이보다 작은 숙련도로는 제한 시간 안에 해결할 수 없으므로 최소 숙련도는 39354입니다.
복잡도 분석
퍼즐의 개수를 N, 최대 난이도를 D라고 하겠습니다.
이분 탐색은 1부터 max(diffs)까지의 범위에서 진행됩니다.
각 숙련도에 대한 판정은 모든 퍼즐을 한 번씩 확인하므로 O(N)입니다.
따라서 전체 시간 복잡도는 다음과 같습니다.
O(N log D)공간 복잡도는 추가 배열을 사용하지 않으므로 다음과 같습니다.
O(1)정리
이 문제는 특정 숙련도로 제한 시간 안에 해결 가능한지를 확인하는 판정 문제로 바꿀 수 있습니다.
숙련도가 높아질수록 총 소요 시간은 줄어들기 때문에 이분 탐색을 적용할 수 있습니다.
숙련도 level을 정한다
→ 전체 소요 시간을 계산한다
→ limit 이하인지 확인한다
→ 가능한 최소 level을 이분 탐색으로 찾는다단조성을 발견하면 쉽게 풀 수 있는 대표적인 이분 탐색 문제입니다.
