[프로그래머스/Lv2] 카펫

문제

출처 : 프로그래머스

테두리 1줄은 갈색으로, 중앙에는 노란색으로 칠해진 카펫이 있다.

갈색 격자와 노란색 격자의 수를 알고 있을 때, 카펫의 크기를 알아내는 방법을 알아내야 한다.

 

갈색 격자의 수가 brown, 노란색 격자의 수가 yellow로 각각 매개변수로 주어질 때, 카펫의 가로, 세로 크기를 크기 순서대로 배열에 담아 반환하는 함수를 만들어야 한다.

 

 

제한조건

1. 갈색 격자의 수는 8 이상 5000 이하의 자연수이다.

2. 노란색 격자의 수는 1 이상 2000000 이하의 자연수이다.

3. 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 길다.

 

 

코드 

from math import sqrt

def solution(brown, yellow):
    A_plus_B = (brown+4) / 2
    A_multi_B = brown + yellow

    w = (A_plus_B + sqrt(A_plus_B**2 -4*A_multi_B)) / 2
    h = (A_plus_B - sqrt(A_plus_B**2 -4*A_multi_B)) / 2

    return [w, h]

 

 

설명

시간이 꽤 걸렸는데도 진전이 없어서 다른 사람의 풀이를 참고했다.

 

이차방정식을 만들어 그 해를 구하는 방식으로 문제를 풀이한다.

 

우리가 구하려는 가로 길이를 w, 세로 길이를 h라고 한다.

갈색 격자의 수와 노란색 격자의 수는 각각 b, y로 표기한다.

 

문제에서 갈색 격자는 사각형의 테두리 1줄을 채우고 있다고 알려줬다.

그렇기 때문에 노란색 격자 부분의 면적은 다음과 같은 식으로 표현할 수 있다. \((w-2)(h-2)=y\)

그리고 총 면적에서 노란색 격자 부분을 빼면 갈색 격자 부분의 면적을 알아낼 수 있다. \(wh-y=b\)

 

w와 h에 대한 식으로 나타내기 위해 식을 풀어본다.

1. \((w-2)(h-2)=y\)

    -> \(wh-2w-2h+4=y\)

 

2. \(wh-y=b\) 식에서 y에 1에서 구한 식을 대입

    -> \(wh-(wh-2w-2h+4)=b\)

    -> \(2w+2h-4=b\)

    -> \(w+h=\frac{1}{2}(b+4)\)

 

3. \(wh-y=b\)

    -> \(wh=b+y\)

 

식을 풀어서 w+h와 wh에 대한 식을 알아냈다.

이제 w와 h를 해로 가지는 \(x^2-(w+h)x+wh\) 이차방정식을 만들 수 있게 됐다.

근의 공식을 통해서 이 이차방정식의 해를 얻는다.

 

$$ w=\frac{(w+h)+\sqrt{(w+h)^2-4wh}}{2} $$

$$ h=\frac{(w+h)-\sqrt{(w+h)^2-4wh}}{2} $$

 

이 때, 문제에서 카펫의 가로 길이가 항상 세로길이보다 같거나 크다고 했으니

w에 루트 앞의 양의 부호가 오도록 해준다.

 

이제 코드로 이 식을 구현한다.

 

A_plus_B = (brown+4) / 2
A_multi_B = brown + yellow

A_plus_B는 w+h를 의미한다.

A_multi_B는 wh를 의미한다.

 

w = (A_plus_B + sqrt(A_plus_B**2 -4*A_multi_B)) / 2
h = (A_plus_B - sqrt(A_plus_B**2 -4*A_multi_B)) / 2

근의 공식을 그대로 옮겨놓은 것

sqrt는 **(1/2)로도 표현할 수 있다.

 

return [w, h]

구해진 w와 h를 배열 형태로 반환한다.