[Programmers] L2. 카펫 (완전탐색/Python)

---

[문제 링크] 👇

프로그래머스

---

풀이 방법

💡 약수 쌍으로 너비와 높이 찾기

 

1️⃣ 전체 격자 수 계산

• total = brown + yellow

2️⃣ 약수 쌍 찾기

• total의 약수를 순회하면서 (width, height) 쌍을 구한다.

3️⃣ 노란색 격자 조건 확인

• 노란색 격자는 갈색 테두리 안에 있어 (width - 2) * (height - 2) == yellow를 만족해야 한다.

4️⃣ 정답 반환

• 조건을 만족하는 (width, height) 쌍을 [width, height] 형태로 반환한다.

Solution

def solution(brown, yellow):
    square = brown + yellow
    for i in range(1, int(square**0.5) + 1):
        if square % i == 0:
            width = square // i
            height = i
            if (width - 2) * (height - 2) == yellow:
                return [width, height]

 

📌 약수를 사용하는 이유

• 카펫의 크기 구하기
  • 갈색과 노란색 격자의 합은 카펫 전체의 넓이가 되므로, 카펫의 가로와 세로 길이는 square의 약수 쌍이어야 한다.
  • 예를 들어, square = width * height와 같이 전체 넓이를 이루는 두 값을 찾는 것이 문제의 핵심인데, 이를 위해 square의 약수를 찾아서 가능한 (width, height) 쌍을 구하는 것이 효율적이다.
• 조건에 맞는 가로와 세로 쌍 찾기
  • 가로와 세로 길이가 (width - 2) * (height - 2) == yellow 조건을 만족해야 하므로, 약수 쌍 중에서 이 조건을 만족하는 (width, height)을 찾는 것이다.

이 방법을 통해 효율적으로 조건을 만족하는 가로와 세로 길이를 구할 수 있다.

 

 

📌 (width - 2) * (height - 2) 

이 조건은 노란색 격자의 개수를 계산하기 위한 것이다. 카펫의 가장자리는 갈색 격자로 둘러싸여 있기 때문에, 전체 너비와 높이에서 양쪽 가장자리 각각 한 칸씩을 제외한 (width - 2)와 (height - 2) 가 노란색 격자가 배치된 공간의 가로와 세로 길이가 된다. 

---

👩‍💻 회고

처음엔 갈색과 노란색의 합의 약수 쌍을 구해서 마지막 값만 반환했었다. 이유는 합이 12라고 했을 때 12의 약수 [1, 2, 3, 4, 6, 12] 에서 중간에 해당하는 [3, 4] 가 정답과 일치했기 때문이다. 그래서 다음과 같이 제출했었다. 

 

오답

def solution(brown, yellow):
    answer = []
    square = brown + yellow
    for i in range(1, int(square**0.5) + 1):
        if square % i == 0 and i == int(square**0.5):
            answer.append(square // i)
            answer.append(i)
            
    return answer

 

그러나 이 코드는 정사각형의 경우에만 작동한다. i 가 가로 또는 세로 길이가 될 수 있어서 square % i == 0 조건만으로 충분했다. 

---