LOAN (하, p. 474)

문제#

어떻게 풀었나?#

2가지 방식으로 풀어봤다.

1. 바이너리 서치로 푼다.

   딱히.. 설명할게 없다.

2. 식을 세워서 푼다.

   첫 잔금: $N$

   1달 뒤 잔금: $NA - C$ (여기서, $A = (1+P/1200)$)

   2달 뒤 잔금: $NA^2 - CA-C$

   3달 뒤 잔금: $NA^3-CA^2-CA-C$

   M달 뒤 잔금: $NA^M - CA^{M-1}-CA^{M-2}-...-C$

   여기서 M달 뒤 잔금이 0이하이면 되므로 그 부등식을 세우면,

   $NA^M - CA^{M-1}-CA^{M-2}-...-C \le 0$

   $\Rightarrow NA^M \le CA^{M-1}+CA^{M-2}+...+C$

   $\Rightarrow NA^M \le C(A^{M-1}+A^{M-2}+...+1)$

   $\Rightarrow \frac{NA^M}{A^{M-1}+A^{M-2}+...+1} \le C$

   $\Rightarrow \frac{NA^M(A-1)}{(A^{M-1}+A^{M-2}+...+1)(A-1)} \le C$

   $\Rightarrow \frac{NA^M(A-1)}{A^{M}-1} \le C$

   $\Rightarrow \frac{NA^M(P/1200)}{A^{M}-1} \le C$

   $\Rightarrow \frac{NP}{1200}\frac{A^{M}}{A^{M}-1} \le C$

   $\therefore \frac{NP}{1200}\frac{A^{M}}{A^{M}-1}$값을 구하면 된다.

   ---

   정답 코드#

   1. 바이너리 서치 방식#

   #include <bits/stdc++.h>
   using namespace std;
   using ll = long long;
   int m;
   double n,p;
   bool Judge(double n, int m, double c) {
       if(n<=0) return true;
       else if(m==0) return n<=0;
   
       return Judge(n*(1.0+p/1200.0)-c,m-1,c);
   }
   int main() {
       ios::sync_with_stdio(false); cin.tie(0);
       int tc; cin >> tc;
       while (tc--) {
           cin >> n >> m >> p;
           double lo=0, hi=2*n;
           for(int z=0; z<100; z++) {
               double mid = (lo + hi) / 2;
               if(Judge(n, m, mid)) hi=mid;
               else lo=mid;
           }
           printf("%.8lf\n", hi);
       }
       return 0;
   }

   2. 식을 세워서 푸는 방식#

   #include <bits/stdc++.h>
   using namespace std;
   double n, p;
   int m;
   double Pow(double x, int n) {
       if(n==0) return 1.0;
       double ret = Pow(x,n/2);
       if(n%2==0) return ret*ret;
       else return ret*ret*x;
   }
   int main() {
       ios::sync_with_stdio(false); cin.tie(0);
       int tc; cin >> tc;
       while(tc--) {
           cin >> n >> m >> p;
           double x = Pow(1.0+p/1200, m);
           printf("%.10lf\n", (n*p/1200)*x/(x-1));
       }
       return 0;
   }