[프로그래머스/Python] 멀쩡한 사각형

문제 설명

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

가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

제한사항

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

 

- 코드

def solution(w,h):
    if w == h : return (w * h - w)
    def gcd(a,b):
        if b==0 : return a
        return gcd(b, a%b)

    if w > h :
        l = w
        s = h
    else :
        l = h
        s = w
    
    g = gcd(l,s)
    return w*h-(w+h-g)

 

- 로직

먼저 가로와 세로가 같은 직사각형, 즉 정사각형인 경우에는 대각선이 지나가는 격자는 가로길이(=세로길이)만큼이다.

가로와 세로를 비교해서 같은 경우에는 가로 * 세로에서 가로길이만큼 빼고 리턴한다.

 

그 외에는 최대공약수를 구해야 하므로 gcd 함수를 선언한다. 유클리드 알고리즘을 이용하는 함수이다.

recursive하게 b가 0이 나올 때까지 gcd를 호출한다.

이때 첫 번째 파라미터가 큰 수로 넣어야 하므로 가로와 세로를 비교해서 l, s 변수를 구해서 파라미터로 넣는다.

직사각형인 경우에 대각선이 지나가는 격자는 (가로 * 세로 - 최대공약수) 만큼이다.

그래서 최대공약수 g를 구해주고 가로*세로한 전체 갯수에서 (가로 * 세로 - g)만큼을 빼서 리턴한다.

 

다른 사람 코드를 보니까 나처럼 큰수, 작은수를 따로 안구해준 거를 보니 테스트케이스에서는 무조건 세로>= 가로인듯하다.

왜 조건에 넣어주지 않았지..?

 

 

 

 

- 문제

https://programmers.co.kr/learn/courses/30/lessons/62048?language=python3

프로그래머스