[프로그래머스/파이썬] 카펫

https://school.programmers.co.kr/learn/courses/30/lessons/42842?language=python3# 

프로그래머스

완전 탐색 문제이다.

 

다른 분들은 변수가 2개 (가로,세로)인 방정식 2개를 세워 연립하거나 근의 공식을 이용해 풀었다

또는

yellow는 최소 1x1 이상인, 사각형 꼴이므로 yellow 타일 개수의 약수를 이용해 식을 풀기도 하였다

 

내 풀이는 3중 for 문을 이용한 정말 '완전 탐색' 풀이이다.

 

시간 복잡도 측면에서 상당히 비효율적이므로 개선할 여지가 있다

def solution(brown, yellow):
    answer = []
    total_len = brown + yellow
    b_buf = brown
    y_buf = yellow
    for width in range(3,total_len+1):
        height = total_len // width
        
        if height > width or width*height != total_len or height < 3:
            continue
        #print(width, height)    
        
        # ex) 3행 4열
        for i in range(height): # 0 1 2
            for j in range(width): # 0 1 2 3
                if i == 0 or i==height-1:
                    brown-=1
                
                elif j==0 or j==width-1:
                    brown-=1
                
                else: yellow -= 1
                
        if brown == 0 and yellow == 0:
            answer.append(width)
            answer.append(height)
            break
            
        else:
            brown = b_buf
            yellow = y_buf
            
        
    return answer