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

문제 요약

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

숙련도에 따라 퍼즐을 풀 때,

각 퍼즐에서 난이도가 숙련도 보다 높다면 난이도 - 숙련도 만큼 퍼즐이 틀리고, 틀린횟수 * (이전시간 + 현재시간)만큼의 시간이 걸린다.
각 퍼즐에서 난이도가 숙련도 보다 낮거나 같다면 현재시간만 투자하면 된다.

이렇게 모든 퍼즐을 푼 시간의 합이 주어진 limit를 넘지 않도록 하는 숙련도(level)의 최솟값을 구하여야한다.

(자세한 문제의 내용은 링크를 참고바랍니다.)

문제 접근

레벨의 최솟값을 구하여야 하기에, 처음에는 diffs 난이도 배열에서 최댓값부터 시작하여 1씩 줄어들도록 푸는 브루트포스를 생각했다.

하지만, 제한사항이 1<=diffs[i]<=100000로 범위가 상당히 크고, diffs의 길이도 1 ≤ diffs의 길이 = times의 길이 = n ≤ 300,000로 제한사항이 주어졌기에

브루트포스 기법은 무조건 시간초과가 날 것이므로 아닌 다른 방식을 생각해내야한다.

결국 level의 값을 효율적이고 시간이 적게 들 수 있게 탐색해내야 하므로, O(nlogn)의 시간 복잡도를 가지는 이분탐색으로 level의 최솟값을 구하면 된다.

풀이

최대 난이도 이상의 값을 탐색하는 것은 의미가 없으므로, 난이도의 최댓값을 구하여, max_diff로 놓은다음 이를 초기에 r로 설정한다. l은 난이도의 최솟값인 1로 두고,

1~max_diff 범위 안에서 레벨의 이분탐색을 진행한다.

현재 레벨을 변수 level로 둘 때,

각 level에서 나올 수 있는 경우는 퍼즐을 푸는 시간의 합이 limit보다 높을 때와 낮거나 같을 때로 나눌 수 있다.

시간의 합이 limit보다 높을 때: 현재 레벨이 낮기에 그런 것 이므로, 더 높은 레벨을 탐색하기 위해 l = level+1 로 둔다.
시간의 합이 limit 보다 낮거나 같을 때: 현재 레벨이 충분히 높기에, 우리는 레벨의 최솟값을 찾아내야 하므로, r = level-1로 두고, 현재 레벨이 답이 될 수도 있기에 answer = level 도 추가해야 한다.

이를 전체 코드로 구현하면 다음과 같다.

전체 코드

  def solution(diffs, times, limit):
    max_diff = max(diffs)
    l = 1
    r = max_diff;
    answer = max_diff;
    while l<r:
        level = (l+r)//2;
        time = times[0]
        for i in range(1,len(diffs)):
            w_count = diffs[i]-level;
            if w_count > 0:
                time += w_count*(times[i-1] + times[i]) + times[i];
            else:
                time += times[i];
        if time>limit:
            l = level+1;
        else:
            r = level;
            answer = level;
    return answer;

느낀 점

한 동안 알고리즘 문제를 안풀었더니 뇌가 굳은게 아닌가 싶다. 그리고 문제 설명 자체가 길고 복잡하면 살짝 길을 잃는 습관이 있는데, 이번 문제에서도 이해해보면 그렇게 어렵지 않은 것 같음에도 불구하고 그런 습관이 나타난 것 같다.

전에 백준에서 풀었던 이분탐색문제랑 거의 흡사했음에도 이분탐색을 빨리 떠올리지 못한게 아쉽다.