프로그래머스 완전탐색 LV2

카펫

문제 설명
Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.
Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항
갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.
입출력 예
brown yellow return
10 2 [4, 3]
8 1 [3, 3]
24 24 [8, 6]

과정

def solution(brown, yellow):
    total=brown+yellow
    factorial=[]
    for i in range(1,total+1):
        if total % i ==0:
            factorial.append(i)
    
    length=len(factorial)
    answer = []
    if length % 2 == 0:
        answer.append(factorial[int(length/2)])
        answer.append(factorial[int(length/2)-1])
    else :
        answer.append(factorial[int(length/2)])
        answer.append(factorial[int(length/2)])
    
    return answer

소인수 분해를 이용해서 이문제를 해결하고자 하였다. 브라운과 옐로우를 합쳐서 통합수를 구한다음 소인수 분해의 가운데 조합을 하면 된다고 생각했다.
하지만
bbbbbbbb
byyyyyyb
bbbbbbbb를 해결하지못한다. b=18 y=6이지만 합치면 24=>[6,4]가 되기때문에 실패가 뜬다.

코드

def solution(brown, yellow):
    total = brown + yellow
    ans = []


    for width in range(total,0,-1):
        if total % width != 0 : continue

        height =int(total/width)
        y = int((width - 2) * (height - 2))
        b = total - y 

        if y == yellow :
            if b == brown :
                ans.append(width)
                ans.append(height)
                break
        
    

    return ans;

따라서 처음부터 시작했다. 가로부분을 처음부터 하나씩 거꾸로 찾으러 가는 식으로 교체하고 노란부분은 항상 가로-2 * 세로-2임으로 이를 구하여 노란색과 갈색이 맞는 경우에만 답을 구해낸다.

참고

def solution(brown, red):
    for i in range(1, int(red**(1/2))+1):
        if red % i == 0:
            if 2*(i + red//i) == brown-4:
                return [red//i+2, i+2]

역시 수학을 잘해야하는듯하다. 절반으로 yellow를 나누고 한줄인지 두줄인지 그이상인지 구하고 그에따라 둘레의 길이를 고려해 답을 내놓는다. ㄸㄸ 미친넘들

참고 2

import math
def solution(brown, yellow):
    w = ((brown+4)/2 + math.sqrt(((brown+4)/2)**2-4*(brown+yellow)))/2
    h = ((brown+4)/2 - math.sqrt(((brown+4)/2)**2-4*(brown+yellow)))/2
    return [w,h]

약수 구해서 하는거같음
ㄸㄷ