[C++] 백준 1145. 적어도 대부분의 배수

문제

입출력

풀이

다섯 개의 자연수 중 최소 세 숫자의 최소공배수를 구하는 문제이다.
두 수의 최소공배수는 두 수의 곱을 두 수의 최대공약수로 나누면 나온다.
근데 세 수의 최소공배수는 어쩌지 하다가
시간도 2초로 넉넉하니 그냥 모든 숫자를 살펴보자 하고 아래와 같이 풀게 됐다.

다섯 개의 자연수는 모두 다르므로 답이 될 수 있는 가장 작은 수는 4이다.
같은 원리로 답이 될 수 있는 가장 큰 수는 마지막 세 수의 곱이다.
while 문을 돌며 어떤 수가 최소 세 개의 수로 나누어 떨어지면,
해당 숫자를 출력하고 끝낸다.

코드

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int arr[5];
	for (int i = 0; i < 5; i++) cin >> arr[i];
	sort(arr, arr + 5);

	int end = arr[2] * arr[3] * arr[4];
	int num = 4;
	while (1) {
		if (num > end) break;
		int cnt = 0;
		for (int i = 0; i < 5; i++) {
			if (num % arr[i] != 0) continue;
			cnt++;
		}
		if (cnt < 3) {
			num++;
			continue;
		}
		cout << num;
		break;
	}
	return 0;
}

채점

잔디용으로 브론즈5 풀다가 에이 그래도 시간을 쓰는건데 하면서 1로 올라옴
절대 골드나 실버는 건드리지 않겠다는 굳은 의지..
(왜..?)