인프런 커뮤니티 질문&답변

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

안녕하세요.

강의 잘 듣고 있습니다.

다름이 아니라.

ll right = 1E18로 지정하면 제출시 틀렸습니다가 뜨고, ll right = 1E15 정도로 하면 정답이 뜨는데,

mid 의 값계산이 잘못되고 있는건가 체크해봐도 오버플로우가 날만한게 없어서. 이유가 궁금합니다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
ll N, M;
vector<ll> A;
ll temp;

bool check(ll mid){

    temp = M;
    for(int i =0 ; i < M ; ++i){
        temp += mid/A[i];
    }

    return temp >= N;
}


int main(){
    cin >> N >> M;
    A = vector<ll>(M,0);
    for(int i = 0 ; i < M ; ++i) cin >> A[i];

    if ( N <= M) cout << N << endl;
    else{

        ll left = 0;
        ll right = 1E18;
        ll ret = 0;
        while(left <= right){
            ll mid = (left+right)/(long long)2;

            if(check(mid)){
                right = mid-1;
                ret = mid;
            }
            else{
                left = mid+1;
            }
        }
        temp = M;
        for(int i =0 ; i < M ; ++i) temp += ((ret-1)/A[i]);

        for(int i =0 ; i < M ; ++i){
            if (ret % A[i] == 0) temp++;
            if (temp ==N){
                cout << i +1 << "\n";
                return 0;
            }
        }
    }
 
    return 0;
}