[Programmers][Python] 멀쩡한 사각형

1. 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/62048

프로그래머스

 

2. 처음 작성한 코드

직사각형을 가로로 길게 눕힌 뒤, x값에 따라 y값을 측정하여 빈칸이 된 상자의 개수를 체크한다.

• 우선 시행 횟수를 줄이기 위해, GCD(최대공배수)를 구한다.
  • GCD는 크기 w x h의 사각형을 gcd 만큼의 크기 (w//gcd) x (h//gcd)의 사각형으로 나눌 수 있다.
  • ex) 12 x 8 사각형 -> 4개의 3 x 2 사각형

최대공배수로 나눈 직사각형 경우의 개수

• x값에 따른 y값을 구한다.
  • x값이 n에서 n+1이 될때 두 x값에 대한 y값의 변화가 있다면 두 개의 정사각형이, y값의 변화가 없다면 하나의 정사각형만 사용할 수 없다.
  • 마지막 x에 대한 경우만 예외로 1을 빼주고 gcd만큼 곱해주면 총 사용할 수 없는 정사각형의 개수가 나온다.
  • 이를 모든 정사각형의 개수 (w x h)에서 빼주면 사용할 수 있는 정사각형의 개수를 구할 수 있다.

      

      

      

    
    

      <python />
    
import math

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

    n_blank_box = 0
    y = 0
    for i in range(1, h//gcd + 1):
        if (w*i)//h == y:
            n_blank_box += 1
        else:
            n_blank_box += 2
            y += 1
    n_blank_box = (n_blank_box - 1) * gcd
    return w * h - n_blank_box

하지만 이렇게 이용한 알고리즘은 w와 h가 최대 1억인 경우에서는 시간초과를 유발한다. 따라서 아래와 수학적 최적화가 필요하다.

 

수학적 최적화를 이용한다.

• 가로가 길기 때문에 기울기가 1을 넘지 못해 결국 y값의 변화에 따른 추가적인 사용 불가능한 정사각형의 개수는 1로 고정이다. 따라서 '가로로 진행되는 x의 개수 + 세로로 추가적인 사용 불가능한 정사각형의 개수 - 마지막 예외'를 계산해 주면 된다.
  • 최소 직사각형으로 계산하면 'h//gcd + w//gcd - 1'이 된다.
  • 이를 경우의 개수 GCD 만큼 곱해주게 되면 'h + w - gcd'가 된다.
  • 따라서 사용할 수 있는 정사각형의 개수는 '(w x h) - (h + w - gcd)'가 된다.

      

      

      

    
    

      <python />
    
import math

def solution(w, h):
    w, h = min(w, h), max(w, h)
    gcd = math.gcd(w, h)
    return w * h - (h + w - gcd)

# 입출력 예시
print(solution(8, 12))

 

3. 다른 코드

수학적인 최적화를 요구한 문제이므로, 사소한 차이는 있으나 크게 다른 코드, 혹은 더 좋은 코드를 발견하지 못했다.