[C++] 백준 24462번: 일어나... 코딩해야지...

문제 링크

24462번: 일어나... 코딩해야지...

문제 요약

알람이 울리기 시작하는 시간과 울리는 주기가 주어진다. 알람 2개를 골랐을 때, 같은 시간에 알람이 울리면 1회 울리는 것으로 친다. 이때, 알람이 울리는 최대 횟수를 구해야한다. 알람이 시작하는 시간은 알람이 울리는 주기로 나누어 떨어진다.

접근 방법

유클리드 호제법을 이용해서 최소공배수를 구한 다음에, 포함과 배제 관계를 잘 처리해주면 되는 문제입니다. 처음에는 그렇게 까다로운 문제가 아니라고 생각하고 풀었다가 보기좋게 함정이란 함정에 다 걸리고 말았습니다. 생각하고 코드 짜는 시간보다 반례 찾는 시간이 더 길었던 것 같습니다.

반례 1

INPUT
2 10
0 4
6 2
OUTPUT
1 2
5

반례 2

INPUT
2 30
5 5
6 3
OUTPUT
1 2
13

반례 3

INPUT
2 10
7 7
6 2
OUTPUT
1 2
4

코드

#include <bits/stdc++.h>

using namespace std;

long long gcd(long long a, long long b) { return (a % b ? gcd(b, a % b) : b); }

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

	int n, d;
	cin >> n >> d;

	vector<pair<long long, long long>> v;
	for (int i = 0; i < n; i++)
	{
		int t, k;
		cin >> t >> k;
		v.push_back({ t, k });
	}

	long long cnt = 0;
	pair<int, int> ans;
	for (int i = 0; i < n; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			if (i == j)
				continue;

			long long g = gcd(max(v[i].second, v[j].second), min(v[i].second, v[j].second));
			long long divisor = g * (v[i].second / g) * (v[j].second / g);

			long long a = ((d - v[i].first) / v[i].second + 1);
			long long b = ((d - v[j].first) / v[j].second + 1);
			long long c = 0;

			if (max(v[i].first, v[j].first) % divisor == 0)
				c = max(v[i].first, v[j].first);
			else
				c = (max(v[i].first, v[j].first) / divisor + 1) * divisor;
			
			if (c <= d)
				c = ((d - c) / divisor + 1);
			else
				c = 0;

			long long tmp = a + b - c;

			if (tmp > cnt)
			{
				cnt = tmp;
				ans.first = i + 1;
				ans.second = j + 1;
			}
		}
	}

	cout << ans.first << ' ' << ans.second << '\n';
	cout << cnt << '\n';
	return 0;
}