[C++]백준 - 1145번 문제

1145번: 적어도 대부분의 배수 (acmicpc.net)

1145번: 적어도 대부분의 배수

 

1145번 : 적어도 대부분의 배수

---

다섯 개의 자연수가 있다. 이 수의 적어도 대부분의 배수는 위의 수 중 적어도 세 개로 나누어 지는 가장 작은 자연수이다.

서로 다른 다섯 개의 자연수가 주어질 때, 적어도 대부분의 배수를 출력하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 다섯 개의 자연수가 주어진다. 100보다 작거나 같은 자연수이고, 서로 다른 수이다.

 

 

출력

---

첫째 줄에 적어도 대부분의 배수를 출력한다.

 

 

---

 

생각해 볼 점

---

적어도 대부분의 배수를 구하려면 결국 모든 3개의 수의  최소 공배수를 비교해봐야 합니다.

 

경우의 수는 5C3이므로 10가지 입니다. 어차피 수행시간이 얼마 안되기 때문에 브루트포스로 진행합니다.

 

5개의 수 중 3개를 뽑아 최소 공배수를 구합니다.

 

최소 공배수를 구하는 방법은, 우선 유클리드 호제법을 이용해 최대 공약수를 구합니다.

 

그 후, 두 수를 곱한 뒤, 최대 공약수를 나눠줍니다.

 

이렇게 구한 최소 공배수와 나머지 한 개의 수의 최소공배수를 구하면 정답입니다.

 

예시 ) 12 , 9, 7

 

12와 9의 최대 공약수 = 3

 

12와 9의 최소 공배수 = 12 * 9 / 3 = 36

 

36과 7의 최대 공약수 = 1

36과 7의 최소 공배수 = 252

 

12, 9, 7의 최소 공배수 = 252

 

 

코드

---

#include <iostream>
using namespace std;

int get_gcd(int a, int b)
{
    if(a < b)
    {
        int temp = a;
        a = b;
        b = temp;
    }
    while(b != 0)
    {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}


int solve(int a, int b, int c)
{
    int gcd = get_gcd(a, b);
    int temp = a * b / gcd;
    gcd = get_gcd(temp, c);
    
    return temp * c / gcd;
}

int main() 
{
    int arr[5] = {0,};
	scanf("%d %d %d %d %d", &arr[0], &arr[1], &arr[2], &arr[3], &arr[4]);
	
	int result = 10000000000;
	for(int i = 0; i < 5; i++)
	{
	    for(int j = i + 1; j < 5; j++)
	    {
	        for(int k = j + 1; k < 5; k++)
	        {
	            int cand = solve(arr[i], arr[j], arr[k]);
	            if(cand < result) result = cand;
	        }
	    }
	}
	printf("%d", result);
	return 0;
}

 

그 외

---