퍼즐 게임 챌린지[자바]
| 문제 원본
https://school.programmers.co.kr/learn/courses/30/lessons/340212
| 문제 설명
당신은 순서대로 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 ≤ 10^15 제한 시간 내에 퍼즐을 모두 해결할 수 있는 경우만 입력으로 주어집니다.
| 문제 풀이
제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 구해야 한다.
첫번째로 접근한 방식은 완전 탐색이다.
숙련도 level을 1부터 100,000까지 순차적으로 확인:
- 모든 가능한 level에 대해 퍼즐을 하나씩 확인하며 제한 시간 내에 모든 퍼즐을 풀 수 있는지 계산.
각 숙련도(level)에서 모든 퍼즐(n)에 대해 소요 시간을 계산:
- level 1부터 100,000까지 총 100,000개의 경우를 시뮬레이션.
- 퍼즐 개수 n의 최대값은 300,000.
이때의 시간복잡도는 O(level * n) 30,000,000,000으로 시간초과
그렇기 때문에 level을 가지고 이분탐색으로 접근했다.
이분탐색으로 접근할 경우의 시간복잡도는 O(n * log(maxLevel)) 18,000,00 으로 충분히 가능하다.
이분 탐색 기본 구조
- start는 최소 숙련도(1), end는 최대 숙련도(100,000)로 설정.
- mid 숙련도로 제한 시간 안에 퍼즐을 해결할 수 있는지 계산.
- 해결 가능: end = mid - 1로 더 낮은 숙련도를 탐색.
- 해결 불가: start = mid + 1로 더 높은 숙련도를 탐색.
- 최종적으로 start에 남은 값이 최소 숙련도.
시간 계산 로직
- 난이도가 숙련도 이하: 단순히 해당 퍼즐의 시간(
time_cur)만 추가. - 난이도가 숙련도 초과: 초과 횟수만큼
time_cur와 이전 퍼즐 재풀이 시간(time_prev) 추가.- 초과 횟수 = diff − level
- 총 소요 시간 = 초과 횟수 *
time_cur+ 초과 횟수 *time_prev+time_cur
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public int solution(int[] diffs, int[] times, long limit) {
int answer = 0;
int start = 1;
int end = 100_000;
while (start <= end) {
int mid = (start + end) / 2;
long time = calculate(mid, diffs, times);
if (time <= limit) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return start;
}
public long calculate(int level, int[] diffs, int[] times) {
long sum = 0;
for (int i = 0; i < diffs.length; i++) {
int diff = diffs[i];
int time_prev = i == 0 ? 0 : times[i - 1];
int time_cur = times[i];
if (diff <= level) {
sum += time_cur;
} else {
sum += (long) (diff - level) * time_cur + (long) (diff - level) * time_prev + time_cur;
}
}
return sum;
}
}