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

Practice
Programmers

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

문제 설명

당신은 순서대로 n개의 퍼즐을 제한 시간 내에 풀어야 하는 퍼즐 게임을 하고 있습니다. 각 퍼즐은 난이도와 소요 시간이 정해져 있습니다. 당신의 숙련도에 따라 퍼즐을 풀 때 틀리는 횟수가 바뀌게 됩니다. 현재 퍼즐의 난이도를 diff, 현재 퍼즐의 소요 시간을 time_cur, 이전 퍼즐의 소요 시간을 time_prev, 당신의 숙련도를 level이라 하면, 게임은 다음과 같이 진행됩니다.

  • diff ≤ level이면 퍼즐을 틀리지 않고 time_cur만큼의 시간을 사용하여 해결합니다.
  • diff > level이면, 퍼즐을 총 diff - level번 틀립니다. 퍼즐을 틀릴 때마다, time_cur만큼의 시간을 사용하며, 추가로 time_prev만큼의 시간을 사용해 이전 퍼즐을 다시 풀고 와야 합니다. 이전 퍼즐을 다시 풀 때는 이전 퍼즐의 난이도에 상관없이 틀리지 않습니다. diff - level번 틀린 이후에 다시 퍼즐을 풀면 time_cur만큼의 시간을 사용하여 퍼즐을 해결합니다.

예를 들어 diff = 3, time_cur = 2, time_prev = 4인 경우, level에 따라 퍼즐을 푸는데 걸리는 시간은 다음과 같습니다.

  • level = 1이면, 퍼즐을 3 - 1 = 2번 틀립니다. 한 번 틀릴 때마다 2 + 4 = 6의 시간을 사용하고, 다시 퍼즐을 푸는 데 2의 시간을 사용하므로 총 6 × 2 + 2 = 14의 시간을 사용하게 됩니다.
  • level = 2이면, 퍼즐을 3 - 2 = 1번 틀리므로, 6 + 2 = 8의 시간을 사용하게 됩니다.
  • level ≥ 3이면 퍼즐을 틀리지 않으며, 2의 시간을 사용하게 됩니다.

퍼즐 게임에는 전체 제한 시간 limit가 정해져 있습니다. 제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 구하려고 합니다. 난이도, 소요 시간은 모두 양의 정수며, 숙련도도 양의 정수여야 합니다.

퍼즐의 난이도를 순서대로 담은 1차원 정수 배열 diffs, 퍼즐의 소요 시간을 순서대로 담은 1차원 정수 배열 times, 전체 제한 시간 limit이 매개변수로 주어집니다. 제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 정수로 return 하도록 solution 함수를 완성해 주세요.

제한사항
  • 1 ≤ diffs의 길이 = times의 길이 = n ≤ 300,000
    • diffs[i]는 i번째 퍼즐의 난이도, times[i]는 i번째 퍼즐의 소요 시간입니다.
    • diffs[0] = 1
    • 1 ≤ diffs[i] ≤ 100,000
    • 1 ≤ times[i] ≤ 10,000
  • 1 ≤ limit ≤ 1015
    • 제한 시간 내에 퍼즐을 모두 해결할 수 있는 경우만 입력으로 주어집니다.
입출력 예
diffs times limit result
[1, 5, 3] [2, 4, 7] 30 3
[1, 4, 4, 2] [6, 3, 8, 2] 59 2
[1, 328, 467, 209, 54] [2, 7, 1, 4, 3] 1723 294
[1, 99999, 100000, 99995] [9999, 9001, 9999, 9001] 3456789012 39354
입출력 예 설명

입출력 예 #1

숙련도가 3인 경우 다음과 같이 진행됩니다.

  • 1번째 퍼즐을 2의 시간을 사용하여 해결합니다.
  • 2번째 퍼즐을 5 - 3 = 2번 틀려서 총 (4 + 2) × 2 + 4 = 16의 시간을 사용하여 해결합니다.
  • 3번째 퍼즐을 7의 시간을 사용하여 해결합니다.

총 2 + 16 + 7 = 25의 시간을 사용하여 모든 퍼즐을 해결할 수 있습니다. 숙련도가 3보다 작은 경우 제한 시간인 30 이내에 모든 퍼즐을 해결할 수 없습니다.

따라서 3을 return 해야 합니다.

입출력 예 #2

숙련도가 2인 경우 다음과 같이 진행됩니다.

  • 1번째 퍼즐을 6의 시간을 사용하여 해결합니다.
  • 2번째 퍼즐을 4 - 2 = 2번 틀려서 총 (3 + 6) × 2 + 3 = 21의 시간을 사용하여 해결합니다.
  • 3번째 퍼즐을 4 - 2 = 2번 틀려서 총 (8 + 3) × 2 + 8 = 30의 시간을 사용하여 해결합니다.
  • 4번째 퍼즐을 2의 시간을 사용하여 해결합니다.

총 6 + 21 + 30 + 2 = 59의 시간을 사용하여 모든 퍼즐을 해결할 수 있습니다. 숙련도가 2보다 작은 경우 제한 시간인 59 이내에 모든 퍼즐을 해결할 수 없습니다.

따라서 2를 return 해야 합니다.

입출력 예 #3

숙련도가 294인 경우 다음과 같이 진행됩니다.

  • 1번째 퍼즐을 2의 시간을 사용하여 해결합니다.
  • 2번째 퍼즐을 328 - 294 = 34번 틀려서 총 (7 + 2) × 34 + 7 = 313의 시간을 사용하여 해결합니다.
  • 3번째 퍼즐을 467 - 294 = 173번 틀려서 총 (1 + 7) × 173 + 1 = 1385의 시간을 사용하여 해결합니다.
  • 4번째 퍼즐을 4의 시간을 사용하여 해결합니다.
  • 5번째 퍼즐을 3의 시간을 사용하여 해결합니다.

총 2 + 313 + 1385 + 4 + 3 = 1707의 시간을 사용하여 모든 퍼즐을 해결할 수 있습니다. 숙련도가 294보다 작은 경우 제한 시간인 1723 이내에 모든 퍼즐을 해결할 수 없습니다.

따라서 294를 return 해야 합니다.

입출력 예 #4

숙련도가 39354인 경우 다음과 같이 진행됩니다.

  • 1번째 퍼즐을 9999의 시간을 사용하여 해결합니다.
  • 2번째 퍼즐을 99999 - 39354 = 60645번 틀려서 총 (9001 + 9999) × 60645 + 9001 = 1152264001의 시간을 사용하여 해결합니다.
  • 3번째 퍼즐을 100000 - 39354 = 60646번 틀려서 총 (9999 + 9001) × 60646 + 9999 = 1152283999의 시간을 사용하여 해결합니다.
  • 4번째 퍼즐을 99995 - 39354 = 60641번 틀려서 총 (9001 + 9999) × 60641 + 9001 = 1152188001의 시간을 사용하여 해결합니다.

총 9999 + 1152264001 + 1152283999 + 1152188001 = 3456746000의 시간을 사용하여 모든 퍼즐을 해결할 수 있습니다. 숙련도가 39354보다 작은 경우 제한 시간인 3456789012 이내에 모든 퍼즐을 해결할 수 없습니다.

따라서 39354를 return 해야 합니다.

풀이과정

이 문제에서는 어떻게 적절한 최소한의 level은 찾는 방법을 구하는 것과

주어진 level에 따라서 시간이 얼마나 걸리는지를 구하는 방법을 구하는 것이 핵심이었다.

특히 주어진 diffs중에서 0번째는 항상 난이도가 1이므로 이를 중심으로 풀어나가야했다.

diff에서 level을 뺀 후에 조심해야할 것은 음수가 time이 음수가 되지 않게 도와주는 것이다.
문제에서는 level이 diff보다 같거나 클 때, time_cur만 소요된다 하였으므로 max를 이용하여 해당 항을 조절할 수 있도록 했다.

1
2
3
4
5
def time_to_solve(level, diff, time_prev, time_cur):
    
    t = (max(0,(diff-level))) * (time_prev+time_cur) + time_cur
    
    return t

주어진 레벨에 따라서 총 소요시간을 구하는 방법.
언제나 첫번째 diff는 time_cur만 소요하므로
time_prev를 0으로 맞춰주고 그 이외에는 times[i-1]를 이용하여
list index out이 일어나지 않도록 해주며 total 소요시간을 구해준다.

1
2
3
4
5
6
7
8
9
10
def get_total_t(level, diffs, times):
    total_t = 0
    for i in range(len(diffs)):
        if not i:
            time_prev = 0
        else:
            time_prev = times[i-1]
        t = time_to_solve(level, diffs[i], time_prev, times[i])
        total_t += t
    return total_t

중요한 것은 최소한의 level을 구하는 것. level이 무작정 높아도 문제는 해결이 되기에
이 문제를 해결할 수 있는 모든 level들을 찾아 그 중 최소값을 구하면 되겠다고 생각했다.
결국 Binary Search를 이용하여 모든 만족하는 level들을 찾아 그 중 최솟값을 answer로.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def solution(diffs, times, limit):
    start = 1
    end = 100000
    candidates = []
    # Binary Search 시작
    while start <= end:
        mid = (start+end)//2
        total_t = get_total_t(mid, diffs, times)
        if total_t > limit:
            start = mid + 1
        else:
            candidates.append(mid)
            end = mid - 1
        print('level, total_t, limit', mid, total_t, limit)
    # 조건을 만족하는 많은 후보들 중에서 minimum을 answer로 내놓는다.
    minimum_level = min(candidates)
    answer = minimum_level
    return answer

Share 0 Comments