[python] 프로그래머스 - 카펫

 

출처 : 프로그래머스 코딩테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/42842

코딩테스트 연습 - 카펫

 

 

풀이

 

def solution(brown, yellow):
    import math
    #yellow의 약수 중 각 +2하고 -4 한게 brown과 같은지 확인
    
    divisors = []
    
    for i in range(1, int(math.sqrt(yellow) + 1)):
        if yellow % i == 0:
            divisors.append([yellow // i, i])
    
    for d in divisors:
        width = d[0] + 2
        height = d[1] + 2
        
        if brown == width * 2 + height * 2 - 4:
            return [width, height]

 

갈색 테두리가 1칸 짜리이므로 가로와 세로의 길이는 각각 yellow의 가로와 세로의 길이에 +2를 한 값과 같다.

갈색의 칸수 즉, 둘레 길이는 가로 * 2 + 세로 * 2 - 각 모서리 4개를 뺀 값과 같으므로

yellow의 약수 모음을 구하고 이를 전부 탐색하며 위 식을 통해 brown의 칸수와 같은지 확인해주면 되겠다.

---

 

시간 복잡도

 

O(N)

 

다른 사람의 풀이를 보면서 알게 된 점

 

-

 

고찰

 

완전탐색 문제는 어려우면 완전 어렵고 쉬우면 완전 쉽네