[백준] 17374 (비트베리)
#PS#BOJ#tier:s1#math

[백준] 17374 (비트베리)

문제 요약

당신은 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+iAP+iA개, 코인 Q′−iBQ'-iB개인데 비트코인을 1개 만들 때 비트와 코인이 1개 필요하므로 min⁡(P+iA,Q′−iB)\min(P+iA,Q'-iB)를 찾으면 그것이 정답이 됩니다.

앞서 살펴본 비트와 코인의 개수는 i에 대한 일차함수로 모델링됩니다. 이때 두 직선 y=P+Axy=P+Ax, y=Q′−Bxy=Q'-Bx가 만나는 점을 구할 수 있는데, 일차방정식을 풀면 x=Q′−PA+Bx=\frac{Q'-P}{A+B}를 얻습니다. 즉, 비트코인의 개수는 i≤Q′−PA+Bi\le\frac{Q'-P}{A+B}일 때는 i가 증가할수록 기울기 A로 증가하고, 그렇지 않을 때는 i가 증가할수록 기울기 -B로 감소하는 함수로 모델링됩니다.

그렇다면 Q′−PA+B\frac{Q'-P}{A+B}의 값만 계산하면 끝날 것 같지만, 이 문제에 등장하는 모든 변수의 값은 음이 아닌 정수여야 한다는 것이 까다로움을 유발합니다. 우리는 정답을 내기 전에 두 가지를 체크해야 합니다:

  1. Q′−PA+B\frac{Q'-P}{A+B}를 y=P+Axy=P+Ax, y=Q′−Bxy=Q'-Bx에 각각 대입했을 때 음수가 되는 것이 하나라도 존재하면 안 됩니다.
  2. Q′−PA+B\frac{Q'-P}{A+B}가 정수가 아니라면, 근처 정수 지점을 함께 탐색해야 합니다.

첫 번째인 음수 가능성부터 봅시다. P+Ax≥0P+Ax\ge0, Q′−Bx≥0Q'-Bx\ge0이 항상 성립하는지 계산해 보면 됩니다. P+AQ′−PA+B=AQ′+BPA+BP+A\frac{Q'-P}{A+B}=\frac{AQ'+BP}{A+B}, Q′−BQ′−PA+B=AQ′+BPA+BQ'-B\frac{Q'-P}{A+B}=\frac{AQ'+BP}{A+B}이므로 이는 참입니다. 따라서 계산할 정답 후보들이 음수일 걱정은 하지 않아도 됩니다.

두 번째로, 당연히 Q′−PA+B\frac{Q'-P}{A+B}가 정수가 아닐 수도 있습니다. 그러면 근처에 좌표가 정수인 지점들인 Q′−PA+B\frac{Q'-P}{A+B}를 올림한 정수값과 내림한 정수값을 탐색해야 합니다. 프로그래밍 언어에 포함된 floor, ceil 함수를 사용해도 되지만, 그러지 않고 푸는 방법도 있습니다. C++에서 (Q' - P) / (A + B)를 계산한 값을 K라고 하면, K−1≤⌊Q′−PA+B⌋≤K≤⌈Q′−PA+B⌉≤K+1K-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일 때만 검사해 보면 정답을 놓치지 않을 수 있습니다.