2022.06.04 [프로그래머스] (python 파이썬) 멀쩡한 사각형

 

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

코딩테스트 연습 - 멀쩡한 사각형

---

풀이

이 문제는 알고리즘 문제라기 보다는 수학문제에 가까운 문제이다.

위의 문제 보기를 보면 8*12의 격자칸에서 대각선이 지나간 사각형은 총 16개이다.

그럼 16이 어떻게 만들어진것인가를 생각해봐야한다.

여기서 w와 h의 합은 20이고 4가 빠져야하는데 여기서 4가 최대공약수가 될 수도 있고 짧은 변/2가 될 수도 있다고 생각했다.

그래서 정사각형으로 생각해보았다.

우선 4*4에서 대각선이 지나간 사각형은 총 4개이다.

그럼 여기서 만약 짧은 변/2를 빼는게 맞다면 16-(4+4-2)=10가 된다. 여기서 답은 12이기 때문에 이 방법은 틀렸다는 것을 알 수 있다.

그래서 최대 공약수를 빼는 방법을 생각해보자.

그래서 4*4-(4+4-4)=12인것을 알 수 있다.

그래서 최대공약수를 구하는 함수를 만들어 위의 방법으로 코드를 작성했다.

def solution(w,h):
    answer = 1
    
    def gcd(a,b):
        while True:
            r=a%b
            if r==0:
                return b
            else:
                a=b
                b=r
    answer=w*h-(w+h-gcd(max(w,h),min(w,h)))
    return answer