728x90
퍼즐 게임 챌린지
https://school.programmers.co.kr/learn/courses/30/lessons/340212


풀이
숙련도(`level`)의 최솟값 + 단조 감소(`level` ↑ -> `total` ↓) => 이분 탐색
1 <= diffs[i] <= 100,000
모든 퍼즐의 난이도 >= 최댓값 -> 절대 실패 X
-> 가능한 `level` 범위: 1 <= level <= max(diffs)
=>`lt = 1`, `rt = 100,000`
- 실패 X -> 1번만
- 실패 O
- 실패 횟수: `diffs[i] - mid`
- 각 실패마다 `time+cur + time_prev`/ 마지막 성공 시 `time_cur`
if (diffs[i] <= mid) total += times[i];
else {
int fail = diffs[i] - mid;
total += times[i] + (long) fail * (times[i] + times[i - 1]);
}
코드
class Solution {
public int solution(int[] diffs, int[] times, long limit) {
int lt = 1;
int rt = 100000;
int ans = rt;
while (lt <= rt) {
int mid = (lt + rt) / 2;
long total = 0;
for (int i = 0; i < diffs.length; i++) {
if (diffs[i] <= mid) total += times[i];
else {
int fail = diffs[i] - mid;
total += times[i] + (long) fail * (times[i] + times[i - 1]);
}
if (total > limit) break;
}
if (total <= limit) {
ans = mid;
rt = mid - 1;
} else lt = mid + 1;
}
return ans;
}
}728x90
반응형
'✏️ > Programmers' 카테고리의 다른 글
| [프로그래머스/Lv.1] 개인정보 수집 유효기간 (Java) (0) | 2026.02.12 |
|---|---|
| [프로그래머스/Lv.1] 성격 유형 검사하기 (Java) (0) | 2026.02.12 |
| [프로그래머스/Lv.1] 비밀지도 (Java) (0) | 2026.02.08 |
| [프로그래머스/Lv.1] 크레인 인형뽑기 (Java) (0) | 2026.02.08 |
| [프로그래머스/Lv.1] 키패드 누르기 (Java) (0) | 2026.02.04 |