반복문 예제 CD굽기

Q.
CD를 굽는 기계가 네개 있다

각각 1분에 1개, 2분에 1개, 3분에 1개, 4분에 1개를 굽는다 가정할 때
CD n개를 굽는데 걸리는 최소 시간은?

A.

최소 공배수가 12이므로

모두가 12개를 굽는 12+ 6 + 4 + 3 = 25개 마다 규칙이 반복될 것이므로 노가다가 가능하다.

하지만 정석 풀이는 다음과 같다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main()
{
	int time = 0;
	int n;
	scanf("%d", &n);

	while (time + time/2 + time / 3 + time / 4 < n)
	{
		time++;
	}

	printf("%d", time);

	return 0;
}

time + time/2 + time/3 + time/4 가 곧 해당 time동안 구울 수 있는 최대 CD의 개수이기 때문에 가능한 풀이이다.

구해야 하는 범위가 너무 커지면 이진 탐색을 통해 다음과 같이 구할 수 있을 것이다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int compare(long long time, long long n)
{
	long long max = time + time / 2 + time / 3 + time / 4;
	long long before_max = (time - 1) + (time - 1) / 2 + (time - 1) / 3 + (time - 1) / 4;

	if (max >= n)
	{
		if (before_max >= n) return 1;
		else return 0;
	}

	else return -1;
}

int main()
{
	long long n;
	scanf("%lld", &n);

	long long left = 0;
	long long right = n;

	while (1)
	{
		long long mid = (left + right) / 2;

		int comp = compare(mid, n);

		if (comp == 1) right = mid - 1;
		else if (comp == -1) left = mid + 1;
		else
		{
			printf("%lld", mid);
			break;
		}
	}

	return 0;
}