Level 2. 멀쩡한 사각형

02. 멀쩡한 사각형

코딩테스트 연습 > Summer,Winter Coding(2019) > 멀쩡한 사각형
https://programmers.co.kr/learn/courses/30/lessons/62048

---

문제 설명

Input value =

• W,H = 정수

Process =

• 대각선으로 잘랐을 때, 1x1 * n 의 영역

Output value =

• 1 x 1 레이어의 갯수(면적)

---

제한 사항

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

문제 구상

#00
W,H = 8,12

#01-1 GCD를 이용

def gcd(a,b):
    return b if a==0 else gcd(b%a, a)
W*H-(W+H)+gcd(W,H)

#01-2 오름차순,내림차순 이용

from math import floor, ceil
result = 0
if W==H:
    result = (H-1)*W
elif W==1 or H==1:
    result = 0
else:
    for i in range(1,W):
        result += (floor(i*H/W)+H-ceil(i*H/W))
result

---

문제 풀이

GCD를 이용한 풀이

01 with 내장 함수

from math import gcd
def solution(W,H):
    return W*H-(W+H)+gcd(W,H)

# Code test
W,H = 8,12
solution(W,H)

02 GCD 함수 생성

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

def solution(W,H):
    return W*H-(W+H)+gcd(W,H)

# Code test
W,H = 8,12
solution(W,H)

오름차순, 내림차순 이용

from math import floor, ceil

def solution(W,H):
    square = 0
    if W==H:
        return (H-1)*W
    elif W==1 or H==1:
        return 0
    else:
        for i in range(1,W):
            square += (floor(i*H/W)+H-ceil(i*H/W))
        return square

# Code test
W,H = 8,12
solution(W,H)