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

문제 설명

가로 길이가 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,h)라고 가정하고

해당 파란색 직선은 (0,0)과 (w,h)을 지난다고 가정하겠습니다.

 

첫 번째로 한 생각은 직선이 격자와 만나는 점 중에서 각 좌표 값이 자연수인 점을 찾아야 된다는 것입니다.

왜냐하면 자연수인 점을 기점으로 같은 패턴을 반복하고 있기 때문에 

가장 처음 나타나는 자연수인 점으로 부터 흰색 사각형 수를 구하고

얼만큼 반복되는지 찾아서 곱해주면 되기 때문입니다.

 

생각해보면 가장 처음 나타나는 자연수인 점은 (w,h)를 공통 인수로 더이상 안나눠질때까지 나눈 점이므로

즉, 각각 좌표를 w,h의 최대공약수로 나눈 점인것을 알 수 있습니다.

 

import math


def solution(w, h):
    gcd = math.gcd(w, h)
    print(gcd)

    local_count = w / gcd + h / gcd - 1
    global_count = local_count * gcd

    answer = w * h - global_count
    return answer

따라서 최대공약수를 gcd라고 한다면

가장 처음 나타나는 자연수인 점은 (w/gcd, h/gcd)이고

해당 점으로부터 발생되는 흰사각형의 갯수는 w/gcd + h/gcd - 1임을 계산을 통해 알 수 있습니다.

 

따라서 해당 패턴은 w,h의 최대공약수만큼 반복되기 때문에

전체 흰사각형의 갯수는 gcd(w/gcd + h/gcd -1) 입니다.

 

 

ps.

최대공약수를 구하고자 할때 파이썬에서는 math 라이브러리에 gcd() 함수를 이용하면 됩니다.

실전에서 매우 유용하겠습니다.

 

다만 공부 목적이나 다른 언어에서는 유클리드 호제법을 이용하여 최대공약수를 구할 수 있습니다.

읽어주셔서 감사합니다!!