[파이썬] 프로그래머스 Summer/Winter Coding(2019) - 멀쩡한 사각형

10월 2주차 #2

 

문제

 

문제

입출력 예

풀이

나중에 문제 제대로 기억을 못할 것 같아서 입출력 예도 넣었다. 의외로 어렵진 않은(?) 문제. 전체 사각형 개수에서 가로 개수, 세로 개수만큼 빼고 중복으로 뺀 사각형의 개수를 다시 더해주면 된다. 이때 중복된 사각형의 개수가 가로, 세로의 최대공약수이다. 

 

빨강 - 가로/파랑 - 세로

허접하지만 이런 느낌. 가로랑 세로를 쭉 한 줄씩 체크하다보면 가로랑 세로를 뺐을 때 겹치는 부분의 개수가 최대공약수! 사실 최대공약수 구하는 법은 검색을 해서 작성했다. 예전에 알고리즘 수업 들을 때 배웠었는데, 유클리드 호제법...을 사용한 방법이라고 한다. 기억이 안 나서 검색해서 사용했지만 이번 기회에 다시 배웠다고 생각해야겠다. 참고로 math를 import하면 gcd함수를 사용해서 그냥 최대공약수를 구할 수 있다. 나는 공부하는 셈 치고 직접 작성해봤다.