'알고리즘' 카테고리의 다른 글
| [BS] 백준 2512 예산 (0) | 2018.04.29 |
|---|---|
| [BS] 백준 1939 중량제한 (0) | 2018.04.29 |
| [BS] 백준 3020 개똥벌레 (0) | 2018.04.29 |
| [BS] 백준 1300 k번째 수 (0) | 2018.04.29 |
| [BS] 백준 3079 입국심사 (0) | 2018.04.29 |
[BS] 백준 1561 놀이공원
2018. 4. 29. 00:46
#include <iostream>
using namespace std;
typedef long long ll;
int n,m;
int tb1[100001];
int main(void)
{
cin >> n >> m;
for(int i=0;i<m;++i){
cin >> tb1[i];
}
if(n<=m){
cout << n << endl;
return 0;
}
ll left = 0;
ll right = 2000000000LL * 1000000LL ;
ll mid;
while(left <= right){
mid = (left + right) / 2;
//cout << mid << endl;
ll st_cnt = 0;
ll st_cnt_min = 0;
st_cnt = m;
for(int i=0;i<m;++i){
st_cnt += mid / tb1[i];
}
st_cnt_min = st_cnt;
for(int i=0;i<m;++i){
if(mid % tb1[i] == 0){
st_cnt_min--;
}
}
st_cnt_min++;
if(n > st_cnt){
left = mid + 1;
}
else if(n < st_cnt_min){
right = mid - 1;
}
else{
for(int i=0;i<m;++i){
if(mid % tb1[i] == 0){
if(n == st_cnt_min){
cout << i+1;
return 0;
}
st_cnt_min++;
}
}
}
}
return 0;
}