[Programmers][Lv.2] 멀쩡한 사각형

https://school.programmers.co.kr/learn/courses/30/lessons/62048

프로그래머스

---

💡IDEA

수학 문제다.

규칙을 찾는 게 중요한데, 처음엔 일차함수처럼 기울기를 사용해서 풀려고 했지만 12번 테스트 케이스가 시간초과가 발생했다.

다시 고민해서 최대공약수를 사용해서 푸는 방법을 생각했다. 최대공약수만큼 중복되는 점을 사용해서 가로+세로-최대공약수 만큼의 사각형을 사용할 수 없게 된다.

2×3 사각형에서 사용할 수 없는 사각형

예시에서 가로 8 세로 12인 경우, 가로 2 세로 3인 사각형이 최대공약수인 4번 반복된다. 이 때 가로 2 세로 3인 사각형에서 행(빨강) 방향으로 3개, 열(파랑) 방향으로 2개인데 가장 첫번째 사각형(보라)은 겹치게 된다. 그래서 2+3-1=4 만큼의 사각형을 사용할 수 없다.

가로 2 세로 3인 사각형은 전체 가로 8 세로 12에서 최대공약수인 4를 나눈 값이기 때문에, 결국 사용할 수 없는 사각형의 총 개수는 2×4 + 3×4 - 1×4 = 8 + 12 - 4 = 16 이 된다. 즉, 가로+세로-최대공약수이다.

사용할 수 있는 사각형은 전체 넓이에서 구한 값을 빼주면 된다.

 

📌CODE

# 12번 테스트 케이스 시간초과
W, H = map(int, input().split())

ans = 0
for i in range(1, W):
    ans += (H*i)//W
    
print(ans*2)

import math

W, H = map(int, input().split())
print(W*H - (W+H-math.gcd(W, H)))