https://school.programmers.co.kr/learn/courses/30/lessons/42842
카펫 문제를 해결하기 위해, 카펫의 크기와 노란색과 갈색 격자의 배치를 고려해야 한다. 문제에서 주어진 갈색 격자 수와 노란색 격자 수를 바탕으로, 카펫의 전체 크기와 노란색 격자의 배치를 만족하는 가로와 세로의 길이를 찾아야 한다.
문제 접근 방법
총 격자의 수: 전체 격자의 수는 brown + yellow
카펫의 크기:
1. 카펫의 가로 길이와 세로 길이는 2 이상의 자연수여야 한다.
2. 카펫의 가로 길이(width)는 세로 길이(height)보다 같거나 커야 한다.
노란색 격자의 배치:
1. 카펫의 테두리를 제외한 노란색 격자 수가 yellow여야 한다.
2. 노란색 격자 수는 (width - 2) * (height - 2)다.
3. 테두리를 포함한 전체 격자 수는 width * height다.
def solution(brown, yellow):
total = brown + yellow
result = []
def backtrack(start, total, yellow):
if result:
return
for height in range(start, total // 2 + 1):
if total % height == 0:
width = total // height
if width >= height and (width - 2) * (height - 2) == yellow:
result.append([width, height])
return
backtrack(3, total, yellow)
return result[0]왜 height는 total // 2 + 1까지만 고려하는가?
가능한 height의 최대 값은 total // 2이다.
이는 height가 total // 2보다 큰 경우, 대응되는 width는 항상 height보다 작거나 같다. 따라서 가로가 세로보다 긴 경우를 만족하지 못한다. height는 최소한의 테두리를 갖추기 위해 3부터 시작한다.
