알고리즘 코드카타 120 - 멀쩡한 사각형

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와 h는 각각 1억까지 값을 가질 수 있다고 한다. 그러므로 주어진 직사각형의 넓이는 최대 1억 * 1억까지 주어질 수 있고 이것을 직접 구하는 것은 불가능하다고 할 수 있다. 따라서 정답을 풀 수 있는 공식을 구해보기로 했다.

 

위의 예시를 보면 직선이  w방향으로 2, h방향으로 3만큼 이동할 때마다 같은 모양이 반복되고 있다. 해당 모양은 2 * 3의 직사각형으로 처음 주어진 직사각형과 닮음이다. 즉, 해당 모양은 원래의 직사각형을 동일한 비율로 축소한 모양이며 최소공배수만큼 축소했을 때 최소가 된다. 그러므로 작은 직사각형이 최소공배수만큼 반복되고 있다는 것을 알 수 있고 따라서 작은 직사각형의 빈칸의 갯수를 세고 최소공배수만큼 곱해주면 전체 빈칸의 수를 구할 수 있다.

 

이제 해당 모양을 0, 0과 2, 3을 통과하는 기울기 3/2의 그래프라고 생각해보자 

 

그래프

y = 3/2 * x 직선이 직사각형을 관통하는 모양이다. 직선이 직사각형을 통과하는 지점에서는 직선이 각 정사각형들의 변을 관통하고 있다. 따라서 해당 지점은 모두 빈칸이 된다. 즉, 직선 y = 3/2 * x 가 직선 y = n과 x = n과 접하는 지점에 있는 정사각형들은 모두 빈칸이라는 의미이다. 따라서 작은 직사각형 하나의 빈칸의 수는 가로, 세로의 길이 - 1이다. (2, 3 지점에서 중첩되기 때문에)

 

작은 직사각형은 위에서 설명한 대로 w, h의 최소공배수만큼 반복되기 때문에 전체 직사각형의 빈칸의 수는 작은 직사각형의 빈칸의 수 * 최소공배수가 된다. 이제 코드를 작성해보자.

 

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

 

가장 먼저 최소공배수를 구하는 함수를 작성한다. math 라이브러리를 사용해도 된다.

 

def solution(w,h):
    a = gcd(w, h)

 

주어진 가로, 세로 길이의 최소공배수를 구해서 반복되는 횟수를 구한다.

 

# def solution(w,h):
#     a = gcd(w, h)
    
    k = w // a + h // a -1

 

작은 직사각형의 가로길이(w // a)와 세로길이(h // a)를 더하고 중복되는 부분을 제거해서 작은 직사각형의 빈칸의 수를 구한다.

 

# def solution(w,h):
#     a = gcd(w, h)
#    
#     k = w // a + h // a -1
    
    return w * h - k * a

 

이제 전체 정사각형의 수 (w * h)에서 전체 빈칸의 수(k * a)를 빼주면 완료!

 

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def solution(w,h):
    a = gcd(w, h)
    
    k = w // a + h // a -1
    
    return w * h - k * a

완료!

 

사실상 코딩보다는 수학문제에 더 가까웠다. 그래도 다른사람의 풀이의 모범답안과 비슷해서 만족스러웠다.