[프로그래머스] Lv2. 카펫

문제

조건

카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.
노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.

풀이

가로와 세로의 길이는 결국 전체 격자 수의 약수들의 순서쌍 중에 있다
갈색과 노란색 격자의 수를 다 합한 다음에 그 수의 약수들을 구해서 하나씩 일치하는지 확인해보는 브루트포스 방식 사용

약수를 구하려는 수의 제곱근까지만 구하면 되고, 문제의 조건에 따라 큰 수를 가로, 작은 수를 세로로 했다.

총 격자의 수 2,000,000

브루트포스로 약수를 계산했을 때, 시간복잡도를 계산했다
2백만이라면 대략 2^10 = 1000이라고 했을 때 2^20 = 1000000, 2^21 = 2000000이 된다. 제곱근은 지수를 2로 나눈 값이므로 2백만의 제곱근은 대략 2^10.5 정도의 값이 되고 1024~2048 사이의 값을 가질 수 있다. 대략 1500 정도만 계산하면 되기 때문에 완전 탐색으로 풀 수 있다.

def solution(brown, yellow):

	# (가로, 세로) 순서쌍이 타일의 수와 일치하는지 여부 
    def check(m, n):
        return 2*m + (n-2)*2 == brown
    
    total = brown + yellow
    for n in range(2, int(total**0.5)+1):
        if total%n == 0 and check(total//n, n):
            return total//n, n