[Python] 프로그래머스 / PCCP 기출문제 / 퍼즐 게임 챌린지

문제 링크

 

프로그래머스 PCCP 문제가 으레 그렇지만, 문제만 읽고는 도통 문제 해석이 쉽지 않다. (얘넨 항상 이런 식임). 이럴 때에는 문제에서 친절하게 제공해주는 예시를 철저히 분석해야 한다.

 

어차피 방정식이 아닌 이진탐색으로 문제를 풀 것이지만, 방정식으로 문제를 이해해보자.

1번 문제의 답, 즉 숙련도를 \(x\)라고 해보자. 그러면 총 소요되는 시간은 다음과 같다:

 

 

i) \(3 \leq x < 5\)

 

2번 퍼즐만 숙련도를 초과하므로 추가시간이 소요된다.
즉 총 소요되는 시간은:

\[
2 + (4 + (5 - x) \times (2 + 4)) + 7 = 43 - 6x
\]

여기서 \(43 - 6x < 30\)이어야 하므로, \(x \in \mathbb{Z}\)인 \(x\)의 최솟값은 3이다.

 

 

ii) \(1 \leq x < 3\)

 

2번과 3번 퍼즐이 숙련도를 초과한다.
그러면 총 소요되는 시간은:

\[
2 + (4 + (5 - x) \times (2 + 4)) + (7 + (3 - x) \times (4 + 7)) = 76 - 17x
\]

여기서 \(76 - 17x < 30\)이어야 하므로, \(x \in \mathbb{Z}\)인 \(x\)의 최솟값은 3이다. 그러나 이는 (ii)의 조건에 맞지 않는다.

 

---

 

자, 이제 문제의 감이 조금 잡혔을 것이다.
이 문제는, diffs 리스트에서 최대 난이도와 최소 난이도의 평균을 초기 \(x\)값으로 잡고, \(x\) 숙련도로 제한 시간 내에 해결이 가능하면 \(x\)를 줄이고, 불가능하면 \(x\)를 늘려가며 이진탐색을 실시하는 것이다.

(\(x = 1\)에서 출발해서 1씩 늘려가는 완전 탐색도 불가능하지는 않겠지만, 아마도 시간복잡도 문제로 테스트 케이스에서 몇 개 틀릴 것 같아서 시도해보지는 않았다.)

 

그리고 꿀팁 : main 코드를 작성할 때, 구현이 복잡하거나 어려운 부분은 "그런 함수가 있겠거니" 하고 일단 짠 다음에, 그 함수를 다음에 코딩하면 문제 풀이가 수월하다.

 

정답 코드

def solution(diffs, times, limit):
    limit_ = limit - sum(times)
    
    if limit_ < 0:
        return -1
    
    n = len(diffs)
    
    trial_time_dict = dict()
    for i in range(1, n):
        trial_time_dict[i] = times[i] + times[i-1]
    
    min_level = min(diffs)
    max_level = max(diffs)
    
    while min_level <= max_level:
        mid_level = (min_level + max_level) // 2
        
        if level_available(diffs, times, limit_, mid_level, trial_time_dict):
            max_level = mid_level - 1
        else:
            min_level = mid_level + 1
    
    return min_level


def level_available(diffs, times, limit_, level, trial_time_dict):
    n = len(diffs)
    cnt = 0
    
    for i, diff in enumerate(diffs):
        if diff > level:
            cnt += (diff - level) * trial_time_dict.get(i, times[i])
            if cnt > limit_:
                return False
    
    return True

 

 

_

loewen.tistory.com