프로그래머스 level2 [멀쩡한 사각형] 파이썬

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

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

처음에는 완전탐색으로 시도했으나 시간초과가 발생하였다.

 

두번째 시도는 (h>=w)인 환경에서 h/w 값을 계산하여, 한 열당 몇개의 사각형이 잘라지는지로 구하였다.

#프로그래머스 멀쩡한 사각형
import math
def solution(w,h):
    if w>h:
        w,h=h,w
    S=w*h
    a=h/w
    cnt= math.ceil(a)*w
    answer=S-cnt
    return answer

 

이 방법이 맞는 풀이라고 생각했는데, 반례가 있는거같았다. (정확한 반례를 찾지는 못했다.)

 

결국, 다른 분들의 도움을 얻어 최대공약수로 풀었다.

#프로그래머스 멀쩡한 사각형
import math
def solution(w,h):
    if w>h:
        w,h=h,w
    S=w*h
    com=math.gcd(h,w)
    answer=S-(h+w-com)
    return answer