글 읽기 - [C++] int 범위에 오류가 있는 것 같습니다.

kms1998 3년 전 0

안녕하세요 c++로 문제를 풀어보았는데요, 알고리즘은 똑같은데 int형 변수로 했을 때는 문제가 생기고 long long형 변수로 했을때는 문제가 풀리는 현상을 보았습니다.

32비트 컴퓨터를 기준으로 int형 변수는 -2,147,483,648 ~ 2,147,483,647의 범위를 갖고 있는것으로 알고 있는데, 이는 2³¹-1이 되는 것으로 알고있습니다. 그리고 문제 에서 범위 또한 0 <= < x < y < 2³¹의 범위를 갖고 있다하여 int형 변수로 충분히 될 것이라고 생각했는데 문제에 오답이 나타나서 글을 올려봅니다.

제 소스 코드는 다음과 같았고 확인 부탁드립니다. 감사합니다.

int main(){
    
    int testCase = 0;
    cin >> testCase;
    
    int* X = new int[testCase];
    int* Y = new int[testCase];
    
    for(int i = 0; i < testCase; i++){
        cin >> X[i] >> Y[i];
    }
    
    for(int i = 0; i <testCase; i++){
       
        int count = sqrt(Y[i] - X[i]);
        
        if(count* count == Y[i] - X[i]){
            cout << 2 * count -1 << endl;
        }
        else if ( ((count * count) < (Y[i] - X[i])) &&
                  ((Y[i] - X[i]) <= (count * (count+1)) )){
            cout << 2 * count << endl;
        }
        else if( ((count * (count + 1)) < (Y[i] - X[i])) &&
                ((Y[i] - X[i]) < ((count + 1) * (count + 1)))) {
            cout << 2* count + 1 << endl;
        }
    }
    
    return 0;
}

slah007 3년 전 1

y-x = count² 이라면 (count + 1)²은 int를 초과할 수 있습니다.

입력 범위에 오류가 있는지는 assert(y<INT_MAX);와 같이 직접 확인 가능합니다.

kms1998 3년 전 0

감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[C++] int 범위에 오류가 있는 것 같습니다.

kms1998 3년 전 0

slah007 3년 전 1

kms1998 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말