[백준 32403] 전구 주기 맞추기 (C++)

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

문제

---

상필이는 크리스마스트리 장식에 사용하려고 N개의 전구를 구매했다. 이 전구에 전원을 연결하면 즉시 빛나지 않고 일정한 주기로 반짝인다. 주기가 t초인 전구는 전원을 연결하고 t초, 2×t초, 3×t초, ⋯가 지난 시각에 반짝인다.

상필이는 모든 전구에 전원을 연결하고 T초가 지난 시각에 모든 전구가 동시에 반짝이게 하고 싶다. 상필이는 전구에 전원을 연결하기 전에, N개의 전구 중 하나를 선택해 그 전구의 주기를 1초만큼 늘리거나 줄일 수 있다. 단, 주기를 1초보다 작아지게 할 수는 없다.

전구의 주기를 조절하는 과정을 통해 모든 전구에 전원을 연결하고 T초가 지난 시각에 모든 전구가 동시에 반짝이게 하려면 이 과정을 최소 몇 번 수행해야 하는지 구해보자.

입력

---

첫째 줄에 전구의 개수 N(1 ≤ N ≤ 1000)과 정수 T(1 ≤ T ≤ 1000)가 공백으로 구분되어 주어진다.

둘째 줄에 정수 a1,a2,⋯,aN(1 ≤ ai ≤ 1000)이 공백으로 구분되어 주어진다. ai는 i번째 전구의 주기가 몇 초인지를 의미한다.

출력

---

모든 전구에 전원을 연결하고 T초가 지난 시각에 모든 전구가 동시에 반짝이게 하려면 이 과정을 최소 몇 번 수행해야 하는지 출력한다.

 

문제 풀이

---

수학 문제.

 

T초에 전구에 불이 켜지려면 전구가 켜지는 주기가 T의 약수여야 한다. T의 약수를 모두 구해 set에 저장한 후, 각 입력마다 가장 가까운 약수와의 차이만큼 전구의 주기를 늘리거나 줄이면 된다.

set에 저장된 수들은 특정 수의 약수이므로 set의 사이즈는 크지 않기 때문에 브루트 포스로 충분히 처리 가능하다. 만약 수가 매우 많았다면 이분 탐색을 사용해 입력보다 큰 수 중 가장 작은 수, 입력보다 작은 수 중 가장 큰 수를 찾아 둘 중 차이가 작은 값을 선택하면 된다.

 

아래는 코드.

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


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

	int N, T;
	int A;
	cin >> N >> T;
	set<int> s;
	set<int>::iterator it;
	int answer = 0;
	for (int i = 1; i <= sqrt(T); i++)
	{
		if (T % i == 0)
		{
			s.insert(i);
			s.insert(T/i);
		}
	}
	for (int i = 0; i < N; i++)
	{
		cin >> A;
		if (T % A != 0)
		{
			int minValue = 123456789;
			for (it = s.begin(); it != s.end(); it++)
			{
				minValue = min(minValue, abs(*it - A));
			}
			answer += minValue;
		}
	}
	cout << answer << "\n";
	return 0;
}