boj 9613번 문제를 통해 배우는 type 설정의 중요성.

처음 분명 아무리 생각해도 제대로 된 방향으로 코드를 작성했다고 생각해서, 거의 12시간 전에 작성한 형태의 코드에서 도저히 어디를 수정해야 하는지 몰라서 계속 고민을 했었는데, 생각을 지속적으로 하다보니까 최대공약수는 서로 같은 수라면 그 수 자체가 된다는 것을 이용해서, 어쩌면 갯수가 100개, 그리고 최대의 값인 1'000'000일 경우 ans값이 int 범위를 넘을수도 있겠다 싶어서 계산을 해보았다

 

100C2의 경우 4950, 그리고 1'000'000으로 모두 원소들이 주어지면, 이 둘을 곱해서 값은 대략 50억정도가 된다. 그래서 이러한 경우면 int 범위를 넘어서므로 ans를 선언할때 long long 으로 변경하여 제출하니까 드디어 성공하였다. 

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

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t,n;
    cin>>t;

    while(t--){
        long long ans=0;
        cin>>n;
        for(int i=0; i<n; i++)
          cin>>a[i];
        for(int i=0; i<n; i++){
            for(int j=i+1;j<n;j++){
                if(a[i]>a[j]) ans+=gcd(a[j],a[i]);
                else ans+=gcd(a[i],a[j]);
                
            }
        }
        cout<<ans<<'\n';
    }
}
/*
100개의 n이 주어지는 경우 경우의 수는 (100)C(2) 이고, 이때의 경우의 수는 99*50 = 4950 가지이고, 이 각각의 경우에 대해서 만약 1'000'000이면 값은 1'000'000* 4950이 된다. 그냥 계산의 편의를 위해 5'000으로 잡으면, 
5'000'000'000의 값이 나오고, 이 값은 50억으로 int의 범위를 넘는다. 
*/

 

이번 문제를 통해서 확실하게 코드를 작성해나가기 전부터 type을 뭘로 설정해야할지 계산을 기반으로 잡고 코드작성을 시작해야 한다는걸 다시한번 상기하게 되었다. 

그리고 나서 참고 코드를 확인해봤을때,

나의 경우는

if(a[i]>a[j]) ans+=gcd(a[j],a[i]);

else ans+=gcd(a[i],a[j]);

의 형태로, 큰 값을 찾아주고 그걸 함수의 뒷부분에 넣어주는 형태로 코드를 작성했는데, 

참고 코드의 경우는 곧바로 ans+=gcd(a[i],a[j]); 형태로 작성한걸 확인할 수 있었다. 

그래서 이에 대해서 생각해보면, 

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

형태로 작성된 gcd 함수에서,

예를들어 12와 10의 gcd를 구할때, 

gcd(12,10); 형태로 사용하게 된다면, 

gcd(10%12,12); 의 값을 재귀적으로 호출할 것이고, 이 값은

gcd(10,12); 가 되어서 결국 gcd 함수는 형태적으로 큰값의 좌우 구분을 해줄 필요가 없이 알아서 큰쪽이 오른쪽으로, 작은쪽이 왼쪽으로 변경되게 되는 과정을 거치게 된다는걸 알 수 있다.

 그래서 gcd함수를 재귀적 형태를 사용해서 위와같이 작성하면 대소비교를 통해서 경우를 나누어서 코드를 작성해줄 필요가 없이

곧바로 ans+=gcd(a[i],a[j]);형태로첨 작성해주기만 해도 된다. 

이걸 이해하고 다음에 이런 경우의 문제를 만나게 되면 대소구분없이 바로 사용하도록 하자.