Notice
Recent Posts
Recent Comments
Link
«   2025/03   »
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31
Tags
more
Archives
Today
Total
관리 메뉴

끄적끄적

프로그래머스 lv2 [멀쩡한 사각형] 본문

코테준비

프로그래머스 lv2 [멀쩡한 사각형]

alstj_성공 2021. 10. 27. 19:24

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

 

코딩테스트 연습 - 멀쩡한 사각형

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을

programmers.co.kr

 

허접한 그림 풀이

 

잘라진 사각형의 개수

 

공식 : (가로+세로) - (가로와 세로의 최대공약수)

최대공약수는 유클리드 호제법을 이용해서 풀면 된다.

주의) 데이터 타입이 long long (w, h가 1억 이하의 자연수이기 때문) 이기 때문에 answer 구할 때 w,h를 long long으로 변환해주어야 한다.