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

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

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

1. 문제이해

 - 최대공약수를 활용하여 축소된 영역을 구하고 전체영역에 대해 계산

 - 수학공식보다 컴퓨터를 활용한 방식으로 계산해보기 (소수점에 대한 계산 등의 이유)

 

2. 코드작성

def solution(w,h):
    answer = w * h

    # 세로로 더 긴 모양의 격자를 만들기위함
    minW = min(w,h)
    maxH = max(w,h)
    
    gcd = 0
    
    # 최대공약수 
    for i in range(minW, 0, -1):
        if w % i == 0 and h % i == 0:
            gcd = i
            break

    minW = minW / gcd # 축소된 격자
    maxH = maxH / gcd # 축소된 격자
    delCnt = 0
    temp = 0
    
    while True:
        temp = temp + minW
        if temp < maxH:
            delCnt = delCnt + 1
        elif temp == maxH:
            delCnt = delCnt +1
            break
        else:
            delCnt = delCnt + 2
            temp = temp - maxH
    
    answer = answer - (delCnt * gcd)
    return answer

아래 while 문에 대해 설명하자면 temp값이 1을 넘어 다음 블록까지 가면 2개를 1을 넘지않으면 1개를 차지한다고 계산하였다. 이런 식이 가능한 이유는 세로로 더 긴 형태의 모양으로 만들어주었기 때문이다.

예시 : (1, 2) : +1 -> (2, 4(1)) +2 -> (3, 3) +1

※ 시간복잡도

O(minW + maxH) => O(n)

 

3. 풀이간 체크사항

 1) 최대공약수 재귀로 구하는 코드

def gcd(a, b): return b if (a == 0) else gcd(b % a, a)