[프로그래머스 42842번] 카펫

문제

번호

완전탐색 | 카펫(프로그래머스 42842번)  

 

내용

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

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

제한사항

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

 

입출력 예

brown	yellow	return
10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

 

언어

JAVA

 

---

풀이

사실... 이번 문제는 완전탐색이라기보다는 수학 문제에 가깝다고 생각한다.

 

우선, 갈색 타일은 노란색 타일의 바깥 테두리 한줄을 이루고 있다. 이는 <pre>전체 타일의 가로 길이 = 노란색 타일의 가로 길이 + 2</pre>와 <pre>전체 타일의 세로 길이 = 노란색 타일의 세로 길이 + 2</pre>임을 뜻한다. 따라서 아래 식이 성립한다.

<pre>

타일의 전체 넓이

= 전체 타일의 가로 길이 X 전체 타일의 세로 길이

= 노란색 타일의 넓이 + 갈색 타일의 넓이

</pre>

 

이제는 완전한 수학 시간이다. 전체 타일의 가로 길이를 $X$, 세로 길이를 $Y$라고 두면,

$X \times Y = brown + yellow$

$(X-2)(Y-2) = yellow$ 이므로,

$X + Y = 2 + \frac {1} {2} \times brown$이다.

 

$(X-Y)^2 = (X+Y)^2 - 4XY$ 임을 이용하면, X, Y를 모두 구할 수 있다.

 

---

코드

import java.util.Arrays;

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = {};
        int sumXY = (brown/2) + 2;
        int subXY = (int) Math.sqrt(Math.pow(2 - brown/2.0, 2) - (4*yellow));
        int X = (sumXY + subXY) / 2;
        int Y = sumXY - X;

        answer = new int[]{X, Y};

        return answer;
    }
}