[BOJ] C++ 1145번 적어도 대부분의 배수

 

https://www.acmicpc.net/problem/1145

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

 

5개의 수 중 적어도 3개의 수의 '배수'이어야하므로

정답은 적어도 input의 가장 작은 값보다는 커야한다.

( = input의 가장 작은 값보다 더 작은 값은 정답이 될 수 없다. 단 하나의 수의 배수도 될 수 없기 때문이다.)

 

따라서 입력 받을 때 min 값을 찾고,

while문을 통해 min값을 시작으로 하나씩 증가시키며 3개 이상의 수로 나눠질 때까지 체크한다.

 

input이 5개이고 각 수가 100 이하,

제한 시간은 2초이므로 해당 알고리즘으로도 충분히 가능하다.

 

---

[BOJ-1145.cpp]

#include <iostream>
using namespace std;

int main() {

	int arr[5] = {};
	int min = -1;
	for (int i = 0; i < 5; i++) {
		cin >> arr[i];
		if (min == -1 || min > arr[i]) min = arr[i];
	}
	

	int cnt = 0;
	int t = min-1;
	while (cnt < 3) {
		t++;
		cnt = 0;
		for (int i = 0; i < 5; i++) {
			if (t % arr[i] == 0) cnt++;
		 }
	}
	cout << t << endl;
}