전세금 N원을 연 이율 P%로 대출받고, 이것을 M(1≤M≤120)개월 동안 매달 일정액 C 원씩 갚는다고 했을 때,

• 대출의 잔금은 대출 금액 N원에서 시작한다.
• 한 달이 지날 때마다 대출 잔금이 월 이자 P/12% 만큼 불어난다.
• 이자가 추가된 다음 월 상환액 C를 대출 잔금에서 줄인다.

이때 M개월 걸려 모든 대출 금액을 다 갚기 위해서는 한 달에 최소 얼마씩 갚아야 할까?

이 문제는 매달 C원씩 대출을 상환할 때 M개월 후의 대출 잔액을 balance(C)라고 하면, 이 문제는 단순히 balance(C) = 0이라는 방정식을 푸는 문제가 된다.

하지만 balance는 M개월이라는 반목문을 이용하는 함수라 역함수를 계산하기 어렵다.

이럴 때 이분법을 쓴다.

// amount원을 연 이율 rates퍼센트로 duration월간 한 달에 monthlyPayment로
// 남았을 때 대출 잔금은?
double balance(double amount, int duration, double rates, double monthlyPayment)
{
	double balance = amount;
	for (int i = 0; i < duration; ++i)
	{
		// 이자가 붙는다.
		balance *= (1.0 + (rates / 12.0) / 100.0);
		// 상환액을 잔금에서 제한다.
		balance -= monthlyPayment;
	}
	return balance;
}
// amount원을 연 이율 rates퍼센트로 duration월 간 갚으려면 한 달에 얼마씩 갚아야 하나?
double payment(double amount, int duration, double rates)
{
	// 불변 조건:
	// 1. lo원씩 갚으면 duration개월 안에 갚을 수 없다.
	// 2. hi원씩 갚으면 duration개월 안에 갚을 수 있다.
	// hi 초기값 : 한 달 후에 전액을 상환하는 경우
	double lo = 0, hi = amount * (1.0 + (rates / 12.0) / 100.0);
	for (int iter = 0; iter < 100; ++iter)
	{
		double mid = (lo + hi) / 2.0;
		if (balance(amount, duration, rates, mid) <= 0)
			hi = mid;
		else
			lo = mid;
	}
	return hi;
}