[완전탐색] 카펫 (JAVA)

# 문제 설명

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]

 

# 정답 코드

public int[] solution(int brown, int yellow) {
        int size = brown + yellow; //전체 격자 개수
        int w = 0; //가로 길이
        int h = 0; //세로 길이

        //size/i * i = size
        for (int i = size; i >= Math.sqrt(size); i--) {
            //w, h는 1, 2가 아님 (yellow는 1 이상이기 때문)
            if ((size % i == 0) && (size / i > 2)) {
                if ((i*2 + 2*(size/i-2)) == brown) {
                    w = i;
                    h = size/i;
                    break;
                }
            }
        }

        int[] answer = {w, h};

        return answer;
    }

 

brown과 yellow의 합으로 전체 격자 개수 size를 구한다.

 

size가 24 + 24 = 48인 경우 나올 수 있는 곱셈식은 다음과 같다.

반복문에서 사용할 식 : i x (size/i) = size

48 x 1

24 x 2

16 x 3

12 x 4

8 x 6

size의 제곱근을 대칭으로 곱셈식이 존재한다.

따라서 size의 제곱근과 같거나 클 때까지만 반복하여 for문의 반복 횟수를 줄여준다.

 

yellow는 1 이상이기 때문에 가로와 세로는 2보다 커야한다.

brown은 카펫의 상단, 하단 줄에 가로만큼 존재한다. (i * 2)

또한 상단, 하단을 제외한 줄에 2개씩 존재한다. (2 * (size / i - 2))

계산값이 brown과 같다면 해당 가로, 세로 길이를 리턴한다.