JArchive 프로그래밍 일기

문제

GCD합 백준 9613번

리뷰

최대공약수 GCD를 구할 줄 알면 풀 수 있는 문제였다.

이중 for문으로 2개의 수를 고른다.

두 수의 최소공배수를 리턴해서 sum에 누적한다.

유클리드 호제법으로 최대공약수를 구하기

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

유의할 점

누적하는 sum 의 자료형는 int가 아니라 long long 으로 써야한다.

수의 개수 n (1 < n ≤ 100)

입력으로 주어지는 수는 1,000,000을 넘지 않는다.

백만과 그 비슷한 크기 수 n개의 모든 쌍의 최대공약수의 합을 누적하려면 int 로는 안된다.

int의 최대 값은 대략 2,147,000,000 이다. (2,147,483,647)

n개가 99이고, 그 주어진 수는 모두 999999 라면. 가능한 쌍은 99 x 98 해서 9702가지 쌍을 만들 수 있다.

99 x 98 x 990,000 = 9,701,990,298

int 의 범위를 초과하기 때문에 sum 변수는 long long 으로 해야 한다.

맞은 코드

#include <iostream> 
using namespace std;

int TC;
int num[101];


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

int main(void){

    cin >> TC;     

       while(TC--){ // 테스트 케이스 만큼 반복 

           long long sum = 0; // 모든 쌍의 GCD 값을 누적할 변수 
        int total = 0;

           cin >> total; 

           for(int i = 0; i < total; i++){ // total 개의 수를 배열에 집어넣는다 
               cin >> num[i];
        }

        for(int i = 0; i < total; i++){ // 이중 for문으로 2개의 수를 골라 GCD를 구한다 

            for(int j = i+1; j < total; j++){
                sum += GCD(num[i], num[j]);
            }    
        }

        printf("%lld\n", sum);
    }

    return 0;    
}