https://www.acmicpc.net/problem/15732
목적
규칙에 맞게 앞에서 부터 도토리를 집어넣었을 경우, 가장 마지막 도토리가 들어가게 될 상지가 어떤건지 구하자.
접근법
1. 규칙에 맞게 다 집어 넣고 답을 구하기에는 일단 집어 넣다가 시간초과에 걸리고 만다. (입력이 상자 100만개, 규칙 만개, 각 규칙 당 C가 1일 경우 10^10의 시간복잡도가 나오므로...)
2. 하나의 방법은 백만개의 상자를 만져서 시간 복잡도를 줄여야 한다. 바로 이분탐색이다. 1부터 백만까지를 범위로 적정 값을 이분탐색해야 한다. (이렇게 하면 20*10^4 정도 되려나..)
3. i번 상자까지 총 몇개의 도토리를 집어 넣었는지는 ... 간단한 수학이다.
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
|
#include<iostream>
#include<cmath>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
int n,k,d,mid,rule[10000][3];
bool possible(){
long long cnt=0;
f(i,0,k)if(rule[i][0]<=mid)cnt+=((min(mid,rule[i][1])-rule[i][0])/rule[i][2]+1);
return cnt>=d;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>k>>d;
f(i,0,k)cin>>rule[i][0]>>rule[i][1]>>rule[i][2];
int l=1,r=1e6;
while(l<=r){
mid=(l+r)/2;
if(possible())r=mid-1;
else l=mid+1;
}
cout<<l;
}
|
문제 설명과 코드에 대한 피드백은 언제나 환영합니다.
다양한 의견 댓글로 남겨주세요.
'Problem Solving > BOJ 백준' 카테고리의 다른 글
[ BOJ 백준 3980번 - 선발 명단 ] 해설 및 코드 (0) | 2019.12.16 |
---|---|
[ BOJ 백준 3090번 - 차이를 최소로 ] 해설 및 코드 (0) | 2019.12.14 |
[ BOJ 백준 2585번 - 경비행기 ] 해설 및 코드 (2) | 2019.12.13 |
[ BOJ 백준 2613번 - 숫자구슬 ] 해설 및 코드 (0) | 2019.12.13 |
[ BOJ 백준 1981번 - 배열에서 이동 ] 해설 및 코드 (0) | 2019.12.13 |