-
33. 멀쩡한 사각형 ⁂코딩 테스트/Level 2 2020. 8. 17. 13:27반응형
https://programmers.co.kr/learn/courses/30/lessons/62048
멀쩡한 사각형
Summer/Winter Coding(2019)
2813명 완료쉽지 않은 문제..
공약수로 나눠서 최소의 단위를 찾는 것 까진 직관적으로 풀리는데...
최소의 단위에서 규칙을 찾는 것이 쉽지 않습니다.
힌트를 드리기도 어렵네요.
힌트 = 정답이라...공약수 관련해서는 이전 유클리드 호제법 포스팅을 참고하세요.
파이썬
import math def solution(w, h): g = math.gcd(w, h) return (h * w) - g * (w / g + h / g - 1)
Java
class Solution { int gcd(int a, int b) { while (b != 0) { int temp = a; a = b; b = temp % b; } return a; } public long solution(int w, int h) { int g = gcd(w, h); return (long) h * w - (long) g * (w / g + h / g - 1); } }
go
func GCD(a, b int) int { for b != 0 { a, b = b, a%b } return a } func solution(w int, h int) int64 { var g = GCD(w, h) return int64((h * w) - g*(w/g+h/g-1)) }
반응형