> 비트베리 > Silver I > #[[수학]] ### 문제 요약 당신은 4종류의 암호화폐 비트, 베리, 코인, 비트코인을 충분히 많이 가지고 있는 친구에게서 아래 다섯 가지 교환을 원하는 만큼 진행할 수 있습니다. 1. 비트 A개 → 코인 B개 획득 2. 코인 B개 → 비트 A개 획득 3. 베리 C개 → 코인 D개 획득 4. 코인 D개 → 베리 C개 획득 5. 비트 1개 + 코인 1개 → 비트코인 1개 획득 정수 A, B, C, D의 값은 테스트 케이스마다 다르게 주어집니다. 현재 당신이 P개의 비트와 Q개의 베리를 보유하고 있을 때, 당신이 가질 수 있는 비트코인의 최대 개수를 구해야 합니다. (정수 P와 Q의 범위는 1만까지입니다) ### 해설 먼저, 비트코인을 만드는 과정에 베리는 관계가 없으므로 모든 베리를 코인으로 바꾸고 시작해도 손해가 없습니다. 베리를 코인으로 다 바꾼 뒤에 Q'개의 코인을 보유하고 있다고 가정하고 해설하겠습니다. 이제 문제 상황을 코인에서 비트로 바꾸는 횟수 i로 모델링해 봅시다. (i가 음수이면, 비트에서 코인으로 바꾸는 것을 |i|번 수행하는 것과 같습니다) 그러면 최종 자산은 비트 $P+iA$개, 코인 $Q'-iB$개인데 비트코인을 1개 만들 때 비트와 코인이 1개 필요하므로 $\min(P+iA,Q'-iB)$를 찾으면 그것이 정답이 됩니다. 앞서 살펴본 비트와 코인의 개수는 i에 대한 일차함수로 모델링됩니다. 이때 두 직선 $y=P+Ax$, $y=Q'-Bx$가 만나는 점을 구할 수 있는데, 일차방정식을 풀면 $x=\frac{Q'-P}{A+B}$를 얻습니다. 즉, 비트코인의 개수는 $i\le\frac{Q'-P}{A+B}$일 때는 i가 증가할수록 기울기 A로 증가하고, 그렇지 않을 때는 i가 증가할수록 기울기 -B로 감소하는 함수로 모델링됩니다. 그렇다면 $\frac{Q'-P}{A+B}$의 값만 계산하면 끝날 것 같지만, 이 문제에 등장하는 모든 변수의 값은 음이 아닌 정수여야 한다는 것이 까다로움을 유발합니다. 우리는 정답을 내기 전에 두 가지를 체크해야 합니다: 1. $\frac{Q'-P}{A+B}$를 $y=P+Ax$, $y=Q'-Bx$에 각각 대입했을 때 음수가 되는 것이 하나라도 존재하면 안 됩니다. 2. $\frac{Q'-P}{A+B}$가 정수가 아니라면, 근처 정수 지점을 함께 탐색해야 합니다. 첫 번째인 음수 가능성부터 봅시다. $P+Ax\ge0$, $Q'-Bx\ge0$이 항상 성립하는지 계산해 보면 됩니다. $P+A\frac{Q'-P}{A+B}=\frac{AQ'+BP}{A+B}$, $Q'-B\frac{Q'-P}{A+B}=\frac{AQ'+BP}{A+B}$이므로 이는 참입니다. 따라서 계산할 정답 후보들이 음수일 걱정은 하지 않아도 됩니다. 두 번째로, 당연히 $\frac{Q'-P}{A+B}$가 정수가 아닐 수도 있습니다. 그러면 근처에 좌표가 정수인 지점들인 $\frac{Q'-P}{A+B}$를 올림한 정수값과 내림한 정수값을 탐색해야 합니다. 프로그래밍 언어에 포함된 `floor`, `ceil` 함수를 사용해도 되지만, 그러지 않고 푸는 방법도 있습니다. C++에서 `(Q' - P) / (A + B)`를 계산한 값을 K라고 하면, $K-1\le\lfloor\frac{Q'-P}{A+B}\rfloor\le K\le\lceil\frac{Q'-P}{A+B}\rceil\le K + 1$이 항상 성립합니다. 따라서 i가 K-1, K, K+1일 때만 검사해 보면 정답을 놓치지 않을 수 있습니다.