[BOJ][Python] 백준 8483번 - Earthquake

문제 링크: https://www.acmicpc.net/problem/8483

---

문제 풀이

유리 등차수열의 내림 합, 정수론

 

$Ax + By > C$를 만족하는 위치에 모든 마천루가 사라졌다는 것은 $ Ax + By ≤ C$를 만족하는 위치에는 마천루가 남아있다는 뜻이다. 그리고 $x ≥ 0$, $y ≥ 0$인 정수 ($x$, $y$) 쌍의 마천루의 개수를 묻는 문제이다.

 

일단 $y$에 대해 식을 정리하면 $y \leq \frac{C-Ax}{B}$이고, 정수 값이어야 하니 $y$의 범위는 $0$부터 $\lfloor \frac{C-Ax}{B} \rfloor$까지. 즉 $\lfloor \frac{C-Ax}{B} \rfloor + 1$개다.

 

$x$도 마찬가지로 $y$가 $0$ 이상의 값을 가지려면, $C - Ax \geq 0$여야 한다. 그러면 자연스럽게 $x \leq \frac{C}{A}$가 되는거고, $x$의 범위는 $0$부터 $ \lfloor \frac{C}{A} \rfloor$까지다.

 

위에서 만족하는 정수 쌍의 개수는 다음과 같이 나타낼 수 있다. $$ \sum_{x=0}^{\lfloor C/A \rfloor} \left( \lfloor \frac{C - Ax}{B} \rfloor + 1 \right) $$

 

상수를 정리하면 최종적으로 다음과 같다. $$ \sum_{x=0}^{\lfloor C/A \rfloor} \left\lfloor \frac{-Ax + C}{B} \right\rfloor + \lfloor \frac{C}{A} \rfloor + 1 $$

 

이렇게 정리하면 앞의 계산은 floor sum으로 구해서 깔끔하게 구할 수 있다.

 

코드