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

 

 

문제 3줄 요약

1. 순서대로 n 개의 퍼즐을 제한 시간 내에 풀어야 한다.

2. 퍼즐 별로 난이도와 소요 시간이 정해져 있다.

3. 숙련도에 따라 틀리는 횟수가 있으며, 틀리면 다시 풀어야 한다. 모두 풀기 위한 숙련도의 최솟값은?

 

---

 

문제가 엄청 길다...

 

쉽게 생각하면

퍼즐을 푸는데 내 숙련도에 따라 한 번에 풀 수 있는 퍼즐이 있고

그렇지 않은 퍼즐이 있는 것이다.

 

제한 시간 안에 풀려면

내 숙련도는 최소 어느 정도는 되어야 하는가 인데..

 

일단 그럼 숙련도에 따라 얼마나 걸리는지 구해야겠죠?

 

입출력이 다음과 같이 주어진다고 할 때

 

def puzzle(diffs, times, limit, level):
    clear_time = 0
    for idx in range(len(diffs)):
        if diffs[idx] <= level: clear_time += times[idx]
        if diffs[idx] > level: clear_time += (diffs[idx]-level)*(times[idx-1]+times[idx])+times[idx]
        if clear_time > limit: return False
    return True

 

난 퍼즐을 제 한 시간 안에 풀 수 있는지 없는지를 판단하는

puzzle 함수를 작성했다.

 

난이도보다 내 숙련도가 같거나 높다면

소요시간만큼만 더해준다.

 

난이도보다 내 숙련도가 낮다면

이전 문제부터 다시 풀어야 한다.

 

따라서 (이전 문제 푸는 시간 + 해당 문제 푸는 시간)을 (난이도 - 숙련도) 만큼

반복한 후에 이제 진짜 풀기 위해 해당 문제 푸는 시간만큼 더해주는 것.

 

그러고 나서

소요된 시간이 제한시간보다 적다면

성공한 거겠죠?

 

사실 이 문제의 핵심은

퍼즐을 푸는 게 아니라

그래서 내 숙련도가 어느 지점이 최소이냐..

그걸 찾는 게 핵심이다.

 

 

가장 난도가 높은 문제를 기준으로

차례대로 숙련도를 1씩 내려가면서 반복문을 돌기엔

마지막 테스트 케이스와 같은 경우는

매우 많은 반복문을 진행하게 된다.

 

따라서 이때 필요한 건

이진 탐색!!

 

고정된 가장 낮은 난이도인 start : 1과

가장 높은 난이도 end를 기준으로 잡아

중간 값을 나의 숙련도로 설정하여 문제를 풀 수 있는지 없는 지를 검사한다.

 

문제를 풀 수 있다면,

내 숙련도를 더 낮춰도 되는 것으로 판단하고

end를 mid 값으로 설정.

 

만약 풀 수 없다면?

내 숙련도를 높여야 하는 것이니

start를 mid 값으로 설정해 주는 방식이다.

 

이를 코드로 구현해 본다면 아래와 같다.

def puzzle(diffs, times, limit, level):
    clear_time = 0
    for idx in range(len(diffs)):
        if diffs[idx] <= level: clear_time += times[idx]
        if diffs[idx] > level: clear_time += (diffs[idx]-level)*(times[idx-1]+times[idx])+times[idx]
        if clear_time > limit: return False
    return True

def solution(diffs, times, limit):
    start, mid, end = 1,0,max(diffs)

    while start<=end:
        mid = (start+end)//2
        
        if puzzle(diffs, times, limit, mid): end = mid-1
        else: start = mid+1
    
    ## start : 1, mid : 1, end : 2 인 경우
    if puzzle(diffs, times, limit, mid): return mid
    if puzzle(diffs, times, limit, mid+1): return mid+1
    return mid-1

 

사실문제 채점 과정에서

14번 테스트 케이스에서 자꾸 틀렸다고 나와서

여기저기 찾아보니..

 

start : 1, mid : 1, end : 2과 같은 케이스는

만일 2의 숙련도가 필요해도

이진 탐색으로는 탐색이 불가한 케이스가 발생한다.

 

이렇게 작은 범위를 고려하여

mid 값과 mid+1 값을 다시 한번 탐색해 주는 코드를 추가하게 되었다.

 

끝!