https://school.programmers.co.kr/learn/courses/30/lessons/340212
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
문제를 보고 조건을 설정해보자.

조건 세우는 건 어렵지 않았다.
이제 남은 건 시간 복잡도 안에 해결을 해야하는데, limits가 10^15였다.
바로 int 범위를 벗어나는... O(n) 해결 시 바로 시간 초과가 뜰 게 분명했다.
그래서 이분 탐색을 생각했다.
O(log(limits)) * n 을 해도 시간초과가 뜨지 않는다!
전체 코드
#include <string>
#include <vector>
#include <algorithm>
#include <climits>
#include <cmath>
using namespace std;
int solution(vector<int> diffs, vector<int> times, long long limit) {
int answer = 0;
long long cnt = 0;
long long lo, hi, mid;
lo = 0;
hi = limit;
// 이분탐색
while(lo + 1 < hi) {
mid = (lo + hi) / 2;
// diff, level 비교
for(int i = 0; i < diffs.size(); i++) {
if (diffs[i] <= mid) {
cnt += times[i];
}
else {
// 틀린 횟수
int temp = (diffs[i] - mid);
int wrong = temp * (times[i-1] + times[i]) + times[i];
cnt += wrong;
}
}
if (limit >= cnt) {
hi = mid;
} else {
lo = mid;
}
cnt = 0;
}
answer = hi;
return answer;
}
반응형
'PS' 카테고리의 다른 글
| [프로그래머스 Lv.2] 석유 시추 (0) | 2025.12.13 |
|---|---|
| [프로그래머스 Lv.2] 도넛과 막대 그래프 (0) | 2025.12.12 |
| [프로그래머스 Lv.2] 비밀 코드 해독 (0) | 2025.12.10 |
| [BOJ 1027] 고층 건물 (1) | 2025.12.09 |
| [프로그래머스 Lv.2] 서버 증설 횟수 (0) | 2025.12.09 |