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

문제 정보

제목 : 멀쩡한 사각형

난이도 : Lv.2

사용 언어 : Python

문제 링크

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

프로그래머스

 

문제 설명

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

 

제한 사항

• W, H : 1억 이하의 자연수

입출력 예

W	H	result
8	12	80

입출력 예 설명

입출력 예 #1
가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다. 원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80 을 반환합니다.

---

나의 풀이

이 문제는 접근 방식이 까다로웠습니다. 여러 사람들의 접근 방식을 참고하며 문제를 풀었습니다. 선분이 정확히 교차하는 곳을 분석해보면 동일한 패턴이 존재하고, 이것은 최대공약수와 관련이 있다는 것을 알 수 있습니다.

패턴이 최대공약수만큼 반복되므로 사용 가능한 직사각형의 수는 '전체 직사각형의 수' - '제외되는 직사각형 수' * '최대공약수'가 됩니다. 이제 제외되는 직사각형의 수를 찾아봅시다.

최소 사각형을 기준으로 하게되면

- W : 2, H : 4의 최소 사각형 (1, 2)의 사각형에서는 2개가 제외됩니다.

- W : 4, H : 6의 최소 사각형 (2, 3)의 사각형에서는 4개가 제외됩니다.

- W : 4, H : 8의 최소 사각형 (1, 2)의 사각형에서는 2개가 제외됩니다.

여기서 규칙을 찾아보면 제외되는 사각형의 개수는 가로 + 세로 -1의 패턴을 가지고 있습니다.

(W,H)의 직사각형에서 못쓰는 사각형의 개수 = gcd * ((W/gcd) + (h/gcd) -1 )
∴ W + H - gcd

공식을 정리 해보면 다음과 같이 나오게 됩니다.

 사용할 수 있는 정사각형의 개수 =  '전체 직사각형의 수' - '제외되는 직사각형 수' * '최대공약수'
∴ answer = ( W * H ) - ( W + H - gcd )

 

유클리드 호제법을 이용해서 최대공약수를 구하고 answer에 위에서 익힌 문제 공식을 사용하여 나온 값을 저장한 후 리턴했습니다. 이번 문제의 접근 방식을 제대로 익혀서 다음에 비슷한 유형의 문제가 나온다면 풀 수 있도록 해야할 것 같습니다.

 

코드

def uc(w,h) :
    if( w > h) :
        w,h = h,w
    while ( h >= 1 ) :
        if( h % w != 0) :
            w,h = h%w,w
        else :
            return w

def solution(w,h):
    gcd_num = uc(w,h)
    answer = (w*h) - ( w + h  - gcd_num )
    return answer