Beelog

programmers.co.kr/learn/courses/30/lessons/62048 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 programmers.co.kr 문제는 위와 같으며, 이 문제는 최대 공약수를 이용하여 문제를 해결할 수 있습니다. 예제를 통해 살펴보면 w = 8, h = 12 일 때, 대각선을 그으면 아래와 같이 작은 직사각형 패턴이 생기는 것을 알 수 있습니다. 작은 직사각형의 크기를 보면 w, h 를 최대 공약수로 나눈 것임을 알 수 있습니다. 따라서 유클리드 호제법을 통해 최대 공약수(G..