Programmers, 구현, Summer/Winter Coding(2019) 중 ‘멀쩡한 사각형’

프로그래머스 Summer/Winter Coding(2019) 중 6208번 ‘멀쩡한 사각형’

https://programmers.co.kr/learn/courses/30/lessons/60057

문제 설명

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

제한사항

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

입출력 예

W : 8, H : 12, result : 80

입출력 예 설명

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

---

풀이

코드를 짜는것보다 문제에 조건에 맞게 생각하는게 상당히 까다로웠던 문제이다.
알고리즘 보다는 고등수학 기하에 가까운 문제였다.

문제에 맞는 격자를 몇개 그리다보면 대각선이 1 * 1 사각형에 만나 교점이 생기는 경우와 생기지 않는 경우로 나뉘는걸 알 수 있다.

교점이 상당히 중요한 분기인데, 이는 교점을 기준으로 같은 모양이 반복되기 때문이다.

교점은 입력으로 주어지는 W와 H의 공배수 마다 생기게 된다. 그러므로 최소공배수인 교점까지 쓰지 못하게 되는 사각형을 구하고, 반복되는 횟수인 최대공약수를 곱하면 전체의 못쓰는 사각형을 알 수있다.

최대공약수와 최소공배수는 모두 파이썬 3.9의 math 모듈에서 gcd 함수와 lcm 함수로 지원한다.

import math

'''
만약 math 모듈을 쓰지 못하거나 직접 알고리즘을 구현해야한다면 
간단히 아래와 같이 가능하다.

유클리드 호제법을 활요한 gcd 알고리즘
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

최대공약수와 최소공배수의 관계를 활용
lcm = w * h // gcd(w, h)
'''

def solution(w, h):
    answer = w * h
    g = math.gcd(w, h)
    l = math.lcm(w, h)
    meet_x, meet_y = l//w, l//h
    answer -= g * (meet_x + meet_y - 1)
    return answer



print(solution(8, 12))