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

 

 문제

 

programmers.co.kr/learn/courses/30/lessons/62048

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

 

 

 

 

 

 

 문제 상황

 

- 가로 Wcm, 세로 Hcm인 종이를 대각선으로 잘라 단위 사각형으로 잘라 쓸 수 없는 부분을 전체에서 제거한다. 

 

 

 

 

 

 

 해결 전략

 

- 전체에서 대각선이 지나가는 사각형을 빼야하고, 결국 반복되는 구조이므로 최소 비율이 몇번 반복되는지 찾아야한다. 이를 위해 GCD(최대 공약수) 개념이 필요하다. 예시의 8cm, 12cm의 경우 비율이 2:3 이므로 가장 작은 가로 2cm, 세로 3cm의 사각형을 기준으로 생각한다. 작은 사각형을 기준으로 가로를 w', 세로를 h'라 할 때 대각선은 w'+h'-1의 사각형 수만큼 지나간다. 그러므로 전체 수는 W*H - (w'+h'-1)*(W//GCD(W,H))이므로 W*H-(W+H-GCD(W,H))가 된다. 

 

 

 

 

 

 

 코드

 

from math import gcd
 
 
def solution(w:int, h:int) -> int:
    return w * h - (w + h - gcd(w, h))
 

 

 

 

 

 

 

 

 

 해설

 

- 파이썬 내장함수로 gcd 구현이 가능하여 매우 간단한 수식이 되지만 간단하게 gcd를 구현해 볼 수 있다. 유클리드 호제법을 사용한다.

 

def gcd(w:int, h:int) -> int:
    if h == 0:
        return w
    return gcd(h, w % h)

 

- 재귀로 gcd를 구현한다. 중요한 것은, 여기서 gcd에 return을 하지 않으면 바로 None이 출력된다.

 

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 알고리즘적으로 복잡한 것이 아니라 수학문제에 가까웠다. 대각선이 지나는 사각형의 개수에 대한 개념을 알고 있는 것이 중요한 문제였다. 이렇게 수학적 지식이 중요한 문제는 Codility에서 주로 봤는데 대비할 필요가 있다.