[코딩테스트] 프로그래머스 - 멀쩡한 사각형 (Lv.2) in Python

가로의 길이 W (cm) 와 세로의 길이 H (cm) 가 주어질 때, 대각선 하나가 그려져있다.

대각선이 지나가지 않는 1cm x 1cm 정사각형의 개수를 구하라.

 

처음의 (비효율적인) 풀이

- 처음에는 사각형의 왼쪽 아래 꼭지점을 (0,0)으로 잡고, 대각선을 y = (h/w)*x로 잡아,

for i in range(1, h):
	width = math.floor(w - w / h * i)
    if width < 1:
    	break
    else:
    	answer += 2 * width

의 방식으로 구했다. 하지만 여기엔 문제점이 있었으니...

 

1. 실수 계산을 포함한다

~> w / h * i 부분에서 실수 계산이 일어나는데,

컴퓨터의 유한한 메모리로 인해 실수는 정확도가 제한된 근사값을 저장하기에 [1],

실수 계산에는 항상 오차가 있을 수밖에 없다.

 

이 문제에서도, 예를들어

w = 2
w / h * i = 0.999999 ... (a)
w / h * i = 1.000001 ... (b)

이라고 치면,

(a)의 경우에는 math.floor(w - w / h * i)의 값이 1이 될 것이고,

(b)의 경우에는 math.floor(w - w / h * i)의 값이 0이 될 것이다!

 

 

가장 좋은 방법은 실수 계산을 아예 안 하는 것인데, 위와 같은 방법으로는 어려워보인다.

 

2. 시간초과 가능성

 

입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해,
1초 당 반복문 수행 횟수가 1억(10^8)을 넘어가면
시간 제한을 초과할 가능성이 있다. [1]

물론 여러 가지 다른 변수들이 있지만, 이를 토대로 했을 때,

위의 코드로는 최악의 경우 (h-1)번을 봐야해서, O(n)이어도 1억에 가깝게 된다.

시간초과의 가능성이 있는 것!

 

실제로 몇 가지 테스트 케이스는 시간 초과가 떴다.

 

효율적인 풀이

이 부분은 결국 질문하기 섹션에서 힌트를 얻었다.

 

가장 중요한 점은, 처음 문제가 너무 크니 문제 자체를 쪼개는 것이다.

 

w, h가 최대공약수 (gcd)를 가진다고 가정했을 때,

최대공약수로 나눈 값들을 w', h'라고 한다.

 

w', h'를 너비와 높이로 하는 사각형의 대각선은

(w' - 1)의 가로선과 (h' - 1)의 세로선을 지나고,

각 선을 지날 때마다 1 x 1 정사각형을 하나씩 지나게 된다.

따라서 대각선이 지나가는 정사각형의 개수는

(w' - 1) + (h' - 1) + 1(처음 정사각형) = w' + h' - 1

 

이 식을 gcd로 곱해주면,

w + h - gcd(w,h)  개수만큼의 정사각형을 대각선이 지나가게 되는 것이다.

 

 

파이썬 구현

import math

def solution(w, h):
    answer = w * h - (w + h -  math.gcd(w,h))
    
    return answer