프로그래머스 - 멀쩡한 사각형

문제 출처 : https://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

 

문제 풀이:

이 문제는 최대공약수 개념을 이용해서 푸는 문제였다. 사실 최대공약수 개념을 직접 생각해내지는 못했다. 문제의 절반밖에 맞지 못했다 하니, 아예 접근이 다르겠거니 했고 도저히 생각나지 않아서 다른 블로그들의 해설을 참고했다. 

 

내가 처음에 접근한 방법은 다음과 같았다. 

import math
def solution(w,h):
    answer = 1
    maximum = max(w, h)
    minimum = min(w, h)
    if minimum == maximum :
        answer = w*w - w
    else:
        answer = w*h - math.ceil(maximum/minimum)*minimum
    return answer

이렇게 하니까 절반은 맞고 절반은 틀렸다.  모든 열마다 같은 수의 사각형만큼을 지나간다고 생각하고 풀어보았다. 틀린 케이스들을 찾기 위해 직접 사각형을 그려 세어보았다. 

이렇게 해보니 첫 번째 열에서는 6개, 두 번째 열에서는 7개, 3번째 열에서는 6개, 4번째 열에서는 7개, 5번째 열에서는 6개를 지나갔다. 결국 이 풀이를 포기하게 되었다. 그리고 찾은 풀이법은 다음과 같다. 2*3의 사각형에서 대각선을 그으면 아래 그림처럼 된다. 

이 때 대각선이 지나가는 사각형의 수는 2 + 3 - 1이 된다. 즉, 일반화하면 가로와 세로의 최대공약수가 1인 경우(서로 나누어질 수 없을 떄)에 대각선이 가로 * 세로 - 1 개의 사각형을 지난다. 그리고 이를 8*12 사각형에서는 4번 반복((2 + 3 - 1)*4), 10*15에서는 5번 반복((2 + 3 - 1)*5)한다. 따라서 일반화하게 되면 대각선이 지나는 사각형의 개수는

가로 + 세로 - gcd(가로, 세로)

가 된다.

 

따라서 전체 사각형의 개수에서 대각선이 지나는 사각형의 개수를 빼면 w*h - (w + h - gcd(w, h))가 된다.

import math
def solution(w,h):
    return w*h - (w + h - math.gcd(w, h))