Search

PGS 퍼즐 게임 챌린지

태그
이분 탐색
매개 변수 탐색
생성일
2024/12/11 12:11

문제 설명

•
제한 시간 내에 모든 퍼즐을 해결할 수 있는 내 최소 숙련도를 찾는 문제
◦
퍼즐의 난이도 ≤ 내 숙련도 → 현재 퍼즐의 소요 시간 만큼 사용
◦
퍼즐의 난이도 > 내 숙련도 → (퍼즐의 난이도 - 내 숙련도) * (현재 퍼즐의 소요 시간 + 이전 퍼즐의 소요 시간) + 현재 퍼즐의 소요 시간

예제 입력/출력

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≤n≤300,0001 ≤ n ≤ 300,000
◦
diffs[0]=1diffs[0] = 1
•
1≤limit≤10151 ≤ limit ≤ 10^{15}
•
제한 시간 내에 퍼즐을 모두 해결할 수 있는 경우만 입력으로 주어짐.

문제 풀이

접근1 브루트 포스 - 상한 O(∣limit∣⋅∣diffs∣)O(|limit| \cdot |diffs|)
접근2 파라매트릭 서치 - 상한 O(n⋅log21015)O(n \cdot log_210^{15})

풀이 코드

접근2 파라매트릭 서치 - 상한 O(n⋅log21015)O(n \cdot log_210^{15})