악곱 == 악성곱슬

수학

---

이 문제는 최대 공약수와 기울기를 이용해서 구현하는 문제이다.

1. 최대공약수, 기울기를 구한다.
2. 가로를 최대 공약수로 나눠서 최대값 만큼 남긴다. 그리고 이 횟수만큼 기울기를 더해보며 네모 칸의 수를 더한다.
3. 전체에서 2에서 구한 값을 뺀다.

이 문제를 풀면서 생각이 난건데 최대 공약수를 구할 필요가 있었을까 싶다. 어차피 Worst Case 는 9999만, 1억이 입력으로 들어온 경우일테고,,,, 내가 구현한 방식 대로라면 오래 걸릴 것이 분명하다.

다음부터는 최악의 케이스를 먼저 고려해보자.

구현

---

from math import gcd, ceil, floor

def calculate(qw, slope):
    count = int(ceil(slope))
    cur = slope
    for i in range(1, qw-1):
        count += int(ceil(cur + slope)) - int(floor(cur))
        cur += slope
    if qw > 1:
        count += int(ceil(slope))
    return count

def solution(w, h):
    if w > h:
        w, h = h, w
    quote = gcd(w, h)
    qw = w // quote
    qh = h // quote
    slope = qh / qw
    print(slope)
    return w*h - calculate(qw, slope)*quote