1️⃣ 문제
2️⃣ 풀이 방법 및 코드
w가 8, h가 12인 위 사각형에서 대각선이 w=2, h=3 크기인 사각형에 대해 꼭짓점이 지나가는 점을 알 수 있다.
w:2, h:3인 사각형의 대각선을 살펴보면,
- x 방향으로 2만큼 선이 지나가고,
- y 방향으로 3만큼 선이 지나가지만,
- 하나의 사각형이 겹치므로 (2와 3은 서로소이지만, 굳이 최대공약수를 따지자면 그것은 1)
- 2 + 3 - 1 = 4인, 4개의 사각형을 사용할 수 없다.
(2,3)은 사실 (8, 12)에 최대공약수(4)로 나눈 값이다. 이 말을 다르게 해석하면 (8, 12) 사각형은 (2,3) 사각형을 4번 반복한 것.
따라서 위 방식으로 w:8, h:12인 사각형의 사용할 수 없는 사각형의 개수는,
4(2 + 3 - 1)
= 4x2 + 4x3 - 4
= 8 + 12 - 4
= w + h - 최대공약수
위 공식으로 대각선이 지나는 사각형의 개수를 구할 수 있으므로, 총 사각형의 개수에 이 값을 빼주면 정답이 나온다.
소스 코드
import Foundation
func gcd(_ a: Int, _ b: Int) -> Int {
if a%b == 0 { return b }
return gcd(b, a%b)
}
func solution(_ w:Int, _ h:Int) -> Int64{
let notUse = w + h - gcd(w, h)
return Int64(w * h - notUse)
}
3️⃣ 이 문제를 풀면서 되새긴 점
최대공약수 구하기
- 유클리드 호제법으로 최대공약수를 구할 수 있다.
func gcd(_ a: Int, _ b: Int) -> Int {
if a%b == 0 { return b }
return gcd(b, a%b)
}