[프로그래머스/Python] 알고리즘고득점Kit-완전탐색-카펫

📌 문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/42842

 

📌 문제설명

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

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

# 제한사항

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

 

 

 

📌 풀이과정 

• 아이디어 
  • 1) 가로 >= 세로 / 2) 모서리 1개씩은 전부다 갈색 ==> 결국 노란색이 어떻게 배치되느냐에 따라 갈색 테두리가 달라진다. 
  • [이하] 노란색 블록개수 세로=yh 가로=yw / 갈색 블록개수 세로=bh 가로=bw 로 표기한다.  
  • 노란색 개수를 인수분해하여 가능한 조합을 만들어봤다. 더 작은 값이 세로여야 한다.
    • 예를 들어, yellow=24이면 가능한 조합은 (1, 24), (2,12), (3,8), (4,6) -> 각각 yh 는 1, 2, 3, 4
  • 계산한 yh 값에 갈색 위 아래 1칸씩만 더 있다고 가정하면, 갈색 세로 값 = 노란색 세로 값 + 2 (bh = yh + 2)
  • 구한 bh 값으로 bw = (갈색 전체 개수 - 세로개수*2) / 2 = (brown - bh*2) / 2 가 된다. 
  • 가능한 조합이 여러 개 나오겠지만, yw <= bw 이어야 한다. 이유는 갈색이 노란색을 둘러싸고 있으니까. 그러면 답을 구할 수 있다. 
• 아래 그림이 위의 아이디어를 구상한 과정이다. 

 

 

📌 풀이코드 

def solution(brown, yellow):
    ylist = []
    for a in range(1, yellow+1):
        if yellow % a == 0:
            b = yellow // a
            if a > b: break 
            else: ylist.append((a,b))
    for yh, yw in ylist: 
        bh = yh + 2
        bw = (brown-2*bh) // 2 
        if yw <= bw:
            return [bw+2, bh]