[프로그래머스 Lv.2] 카펫 (파이썬 풀이)

문제 링크

프로그래머스

 

[풀이 2]

* 카펫의 가로, 세로 각각의 격자의 수는 모든 격자의 수의 약수이다.

* 즉, 모든 격자의 수 ÷ 세로 격자의 수 = 가로 격자의 수

* 노란색 격자의 수 = (카펫의 가로 격자의 수 - 2) * (카펫의 세로 격자의 수 - 2)

* 노란색 겉 테두리 1줄은 갈색 격자로 이루어져야 하므로 카펫의 가로, 세로 격자의 최소 수는 3 이상이다.

 

1. 갈색과 노란색 격자의 수를 모두 더하여 총 합을 구한다.
2. 3이상, 총 합 이하의 수를 차례로 대입하여 다음 식이 성립하는 약수 y를 찾는다.
   • {(총 합 ÷ y) - 2} * (y - 2) = 노락색 격자의 수
3. 위 식이 성립하는 순간의 (총 합 ÷ y) 는 가로 격자의 수, y는 세로 격자의 수가 되므로 [(총 합 ÷ y), y] 를 반환한다.

[코드 2]

def solution(brown, yellow):
    total = brown + yellow
    for i in range(3, total):
        if total % i == 0 and ((total // i) - 2) * (i - 2) == yellow:
                return [(total // i), i]

---

[풀이 1]

1. 갈색과 노란색 격자의 수를 모두 더하여 총 합을 구한다.
2. 총 합의 약수를 구한다.
3. 약수 x와 약수 y의 곱이 총 합이면서 x-2와 y-2가 노란색 격자의 수인 경우를 찾는다.
   • 갈색은 노란색의 테두리 한 줄만 차지하기 때문에 노란색은 갈색의 가로, 세로 길이보다 각각 2씩 작은 길이를 취한다.
   • 약수가 홀수인 경우 정중앙의 한 숫자를 각각 x와 y로 잡고 시작, 약수가 짝수인 경우 중앙의 한 쌍의 숫자중 큰 수를 x, 작은수를 y로 두고 시작한다.
   • (x*y=총합, (x-2)*(y-2)=노란색 수) 위에서 설정한 x와 y를 대입하여 해당 식을 만족하지 못하는 경우 x를 한 단계 높은 수의 약수로, y를 한 단계 작은 수의 약수로 설정한다.
   • 같은 방법으로 해당 식이 성립할 때까지 반복한다.
4. 식이 성립하는 경우를 찾으면 그때의 [x, y]를 반환한다.

[코드 1]

def solution(brown, yellow):
    total, cd = brown + yellow, []
    for number in range(1, total+1):
        if total % number == 0:
            cd.append(number)
    a, b = divmod(len(cd), 2)
    x, y = (a, a) if b else (a, a-1)
    while (cd[x]-2) * (cd[y]-2) != yellow:
        x += 1; y -= 1
    return [cd[x], cd[y]]