인프런 커뮤니티 질문&답변
작성한 질문수
6-J 질문 드립니다.
해결된 질문
작성
·
186
1
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
typedef long long ll;
ll n, m, ans, last_su;
ll a[10004];
int check(ll mid){
ll cnt =0;
for(int i=0; i<m; i++){
cnt += mid / a[i] + 1;
}
return cnt >= n;
}
ll last_check(){
ll cnt=0;
for(int i=0; i<m; i++){
cnt += (ans-1) / a[i] + 1;
}
return n - cnt;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
for(int i=0; i<m; i++){
cin >> a[i];
}
// 이 부분
ll l=0, r=6*1e10+4;
while(l <= r){
ll mid = (l+r)/2;
if(check(mid)){
r = mid-1;
ans = mid;
} else{
l = mid+1;
}
}
if(ans){
last_su = last_check();
}else{
cout << n << '\n';
return 0;
}
vector<ll> v;
for(int i=0; i<m; i++){
if(ans % a[i] == 0){
v.push_back(i+1);
}
}
cout << v[last_su-1] << '\n';
}
다른 부분은 아니고 위의 코드를 제출 했을 때 정상적으로 맞았다고 나오는데, 시험삼아 while(l<=r) 위의 줄에서, 이분탐새하기 직전 l과 r을 선언하는 줄에서
r = 1e18로 정의하였을 때 오답이 나옵니다.
1e18도 long long의 범위 이내인데 어째서 오답이 나오는지 모르겠습니다.
답변 1
1
큰돌
지식공유자
안녕하세요 토모시키님 ㅎㅎ
보통의 long long 문제는 1e18로 해도 정답이 나옵니다.
보통은 그렇게 해도 풀린다고 생각을 일단 가지시구요.
그게 안될 경우에는 문제에서 주어진 범위를 기반으로 최댓값을 잡으셔서 진행해주셔야 합니다.
이문제같은 경우
bool check(ll mid){
temp = m;
for(ll i = 0; i < m; i++)temp += mid / a[i];
return temp >= n;
}이부분이 문제가 뜨는 코드가 됩니다.
mid에 1e18 / 2 가 들어갔을 경우 계속해서 더하다 보면 temp가 long long의 범위를 초과하는 경우의 수가 발생되게 됩니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.