BOJ 13199, 치킨 먹고 싶다
ProblemSolving ·이 문제는 등비 수열의 합과 극한 값을 이용한 수학 문제입니다.
풀이
치킨 한 마리 가격 : 2000원
가진 돈 : 10만원
한 마리당 필요 쿠폰 : 10개
한 마리당 주는 쿠폰 : 3개
라고한다면 ?
두영 50마리 + 쿠폰 150개
=> 50마리 + 15마리
=> 65마리
상언 50마리 + 쿠폰 150개
=> 50마리 + 15마리 + 쿠폰 45개
=> 50마리 + 15마리 + 4마리 + 쿠폰 17개
=> 50마리 + 15마리 + 4마리 + 1마리 + 쿠폰 10개
=> 50마리 + 15마리 + 4마리 + 1마리 + 1마리 + 쿠폰 3개
=> 71마리 + 쿠폰 3개
상언이가 쿠폰으로 추가로 먹을 수 있는 치킨의 수
=> 쿠폰 150개 / 10 + 쿠폰 45개 / 10 + 쿠폰 17개 / 10 + 쿠폰 10개 / 10 + 쿠폰 3개 / 10
첫 항을 a1이라고 한다면?
=> a1 + a1 * (3/10) + a1 * (3/10) * (3/10) +a1 * (3/10) * (3/10) * (3/10)
=> a1(1 + (3/10) + (3/10)(3/10) + (3/10)(3/10)*(3/10))
=> a1 * (1 - (3/10)의 n제곱) / (1 - (3/10))
0마리를 계속 먹는다고 생각한다면 n은 무한이나 다름없다.
-1 < r < 1이라면 r의 n제곱은 0에 수렴한다.
=> a1 * 1 / (7/10)
=> a1 * (10/7)
=> 150/10 * 10/7
=> 150/7
=> 가진 쿠폰 / (한 마리당 필요 쿠폰 - 한 마리당 주는 쿠폰)
하지만 그대로 사용했더니 오차 발생했습니다…
21개의 쿠폰이 있다고 생각한다면 21 / (10-3) 으로 3마리를 추가로 먹을 수 있다고 계산이 됩니다.
실수의 경우
21/10 + 7/10 + 2.1/10 하면 3마리까지 나오나
문제의 경우
21/10 + 7/10 이므로 2마리밖에 못먹는다.
치킨 한 마리만큼의 쿠폰을 빼놓으면 해결…!
1 + 11/10 + 3.3/10 + 0.99/10 => 2마리
1 + 11/7 => 2마리
#include<iostream>
#include<algorithm>
using namespace std;
int t;
int main() {
cin.tie(NULL);
cout.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> t;
while (t--) {
int chicken, money, require, coupon;
cin >> chicken >> money >> require >> coupon;
int s = (money / chicken);
int c = (money / chicken) * coupon;
// 등비수열의 합 공식에 극한값 대입
if (c >= require) {
c -= require;
s += 1;
s += c / (require - coupon);
}
int d = (money / chicken) + ((money / chicken) * coupon) / require;
cout << s - d << '\n';
}
return 0;
}