boj 5347번 문제 LCM을 통해 배우게 되는 계산 중간 과정에서의 int overflow의 가능성. 그리고 해결법 세가지.

처음 코드를 작성해서 예제코드에서 정상적으로 동작하는것을 확인하고 제출을 하였을때,

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b){
    if(a==0) return b;
    return gcd(b%a,a);
}

int lcm(int a, int b){
    return a/gcd(a,b)*b;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int a, b;
        cin>>a>>b;
        cout<<lcm(a,b)<<'\n';
    }
}

이러한 형태로 코드를 작성하였고, 제출했을때 틀렸습니다를 받게 되었다. 그런데 길게 생각해보아도 이 코드가 논리적으로는 옳바른 흐름을 가진것 같아서 잘못된 부분이 무엇이 있을까 싶었는데, 이때에 lcm을 구하면서 입력으로 주어지는 값들이 1'000'000 까지의 수들이기 때문에 최소공배수를 구 하면 상황에 따라서 최소공배수의 사이즈가 커져서 int의 범위인 대략적으로 2'100'000'000(21억)을 넘을 수 있겠다 싶어서 이 코드를 아래의 코드처럼 수정하였다. 

 

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b){
    if(a==0) return b;
    return gcd(b%a,a);
}

long long lcm(int a, int b){
    return a/gcd(a,b)*b;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int a, b;
        cin>>a>>b;
        cout<<lcm(a,b)<<'\n';
    }
}

근데 이 코드를 제출하여도 계속해서 틀렸습니다를 받게 되었는데,  지속적으로 생각해봐도 결국 논리는 맞는것으로 보여지고, 코드의 흐름도 문제가 될 부분이 있다고 생각되지 않아서 도대체 어디가 잘못된걸까 생각을 계속 해봐도, 잘못된 부분이 어디인지를 모르겠었는데, 

이때에 long long 을 반환한다고 lcm을 짜놓았지만, 내부적으로 들여다보면 계산하는 값들은 모두 a, b , gcd(a,b)들 끼리의 연산인데, 이때에 a/gcd(a,b)*b의 과정에서 결국 연산되는 요소들은 모두 int 범위이고, 그 값을 return을 통해서 long long 으로 담기만 할뿐 연산과정중 요소들의 type은 int 범위이기 때문에 저 내부 연산 과정에서 int overflow가 발생할 수 있겠다 싶어서 이번에는 아래와 같이 수정해보았다. 

 

#include <bits/stdc++.h>
using namespace std;

long long gcd(long long a, long long b){
    if(a==0) return b;
    return gcd(b%a,a);
}

long long lcm(long long a, long long b){
    return a/gcd(a,b)*b;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        long long a, b;
        cin>>a>>b;
        cout<<lcm(a,b)<<'\n';
    }
}

결국 내가 마지막에 수정한 부분은, lcm을 long long으로 반환하고, 그 내부 연산에 참여하는 모든 요소들도 모두 long long으로 선언해서 내부 연산 과정인 a/gcd(a,b)*b에서 int 범위를 넘어서는 int overflow를 피하기 위해 만들었고, 이렇게 계산 과정에 모두 참여하는 원소들을 long long 범위로 선언하고 난뒤에 제출해서야 드디어 맞았습니다. 를 받을 수 있었다. 

 

결국 int overflow를 피하기 위해서는, 어떠한 타입의 값으로 반환하겠다 라는 부분만 범위가 맞는 type으로 선언해주면 안되고, 그 과정에 참여하는 원소들도 모두 type이 맞게 바꾸어주어야 원하는 결과를 얻을 수 있는 것이다. 

 

+++++++++++++++++++++++

혹은 방금 이 글을 작성하면서 의문점이 들어서 코드를

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b){
    if(a==0) return b;
    return gcd(b%a,a);
}

long long lcm(int a, int b){
    return (long long)a/gcd(a,b)*b;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int a, b;
        cin>>a>>b;
        cout<<lcm(a,b)<<'\n';
    }
}

이런식으로 중간 부분만 return (long long) a/gcd(a,b)*b; 형태로 작성해보았는데, 제출하였을때 맞았습니다 를 받을 수 있었다. 

결국 저 부분이 그냥 int들 끼리의 연산으로만 두면 결국 return 형태가 int가 되고, 그때에 int overflow가 발생할 수 있는 부분이었기 때문에, 저 부분을 형변환해서 long long타입으로 만들어주니까 통과할 수 있었다. 

이렇듯 큰 수 들 끼리의 연산에서 내부에 어떤 타입들끼리의 연산인지 정확하게 파악하고, 그렇게 그 원소들끼리의 연산을 그대로 두면 int 타입으로 반환되면서 중간에 int overflow가 발생할 수 있다는걸 알고, 그에 맞게 전체 참여 원소들을 long long으로 선언해주던지, 혹은 결과를 앞부분에 (long long)으로 캐스팅 해주던지 해서 결과값이 int oveflow가 되지 않도록 만들어주자. 

 

+++++++++++++++++++++++=

추가적으로 

코드들을 볼때, 1ll* 형태를 통해서 1ll 같은 수를 곱해서 long long 타입으로 만들어서 over flow를 피하는 것을 보았는데, 그래서 한번 

return 부분에 1ll을 곱해서 return 1ll*a/gcd(a,b)*b; 형태로 작성하면 어떻게 될까(다른 모든 참여원소들을 int로 선언한뒤에)

싶어서 한번 그렇게 코드를 작성했는데, 이것도 통과할 수 있었다. 

이로써 해결 방법으로는 내가 현재까지 알아낸 방법은, 

참여 원소들을 모두 long long 으로 선언하기, 앞에 (long long) 을 붙여서 캐스팅 하기, 1ll*을 곱해서 캐스팅하기. 이렇게 3가지를 들 수 있겠다. 다음에는 꼭 int overflow의 위험이 있을때 처음부터 3가지 방법을 모두 떠올려서 문제를 해결하기 위해서 방향을 잡아보도록 하자. 

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b){
    if(a==0) return b;
    return gcd(b%a,a);
}

long long lcm(int a, int b){
    return 1ll*a/gcd(a,b)*b;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int a, b;
        cin>>a>>b;
        cout<<lcm(a,b)<<'\n';
    }
}