[알고리즘 프로그래머스] 카펫 (LEVEL 2)

(문제) 카펫 (LEVEL 2) [완전탐색]

---

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]

---

해결방법

방법1 Brown 사용하여 넓이로 접근

수학적 방법으로 도달해야 하는 문제다.

우리가 먼저 알아야하는 것은 갈색은 네모의 테두리 이다.

네모의 테두리의 개수를 구해보자.

갈색의 개수를 구하는 공식은 다음과 같다.

(가로 + 세로 - 2) * 2 이다.

필자는 처음에 “왜??” 라는 의문을 품었다. 하지만 필자는 엄청 멍청해서 이해를 못했던 것이다.

자 그림을 통해 예를 들어보겠다.

일단 네모의 규칙은 각 마주보는 모서리의 길이는 서로 같다는 것이다.

그러면 아래와 같이 각각 영역을 나눌 수 있는데, 이 때 겹치는 곳이 2 곳 있다.

자 그 영역 중, 한 곳만 생각을 해보겠다.

각각 가로와 세로의 길이를 더하면 겹치는 곳 1곳이 생긴다.

겹치는 곳 중 가로 혹은 세로 한 곳을 빼면 이런 형태가 될 텐데

여기서 다른 나머지 곳도 빼면, 딱 반대 쪽의 개수와 같아진다!

그래서 공식은 (가로 - 1 + 세로 - 1) * 2 가 될 수 있는 것이다.

자! 이제 공식을 이용해서 구했으니 우리는 이 하나의 공식을 이용해서 가로와 세로의 길이를 유추할 수 있다.

하지만 아직 식 하나가 더 필요하다.

그 공식은 안에 있는 노랑색을 이용하는 것이다.

노랑색의 개수는 (가로 * 세로) 즉, 네모의 넓이를 구한 후 brown을 빼면 나온다.

우리는 이렇게 총 2개의 공식을 얻을 수 있다.

[w는 가로 h는 세로]

wh - brown = yellow
(w-1 + h-1) * 2 = brown

이제 2중 for문을 이용하여 가로와 세로의 길이를 구한다.

이때 가로 세로 길이는 무조건 3 이상이 될 수 밖에 없으므로 3 부터 시작한다.

하지만 이 방법의 단점은 2중 for문을 이용하므로 시간 복잡도가 n^2 이 든다는 점이다.

이것보다 더 뛰어난 성능을 할 수 있는 방법이 있다.

그것은 아래와 같은 방법이다.

방법2 Yellow 사용하여 둘레로 접근

Yellow 와 붙어 있는 Brown의 개수는 총 Brown - 4 개와 같다.

이유는 아래 그림과 같이 알 수 있다.

그러면 Yellow 줄 기준(약수)으로 생각할 수 있다.

만약 Yellow 가 4일 경우 Yellow는 2x2, 4x1의 경우가 나온다.

즉 1줄 혹은 2줄로 표현 할 수 있는 것이다.
(약수 개)

반복문을 돌리면 세로 혹은 가로의 개수를 알 수 있다.

반복문의 Yellow개수의 약수로만 가능하므로 반복문 순회 범위는 Yellow개수 ** 0.5 + 1 만큼만 하겠다.

반복문에서 사용할 순회는 “세로”로 기준을 잡아보자!

만약에 Yellow개수 가 나누어 떨어지면, 반복문에 사용한 i 를 “세로”라고 하면 Yellow개수 / i 를 하면 “가로”가 된다.

우리는 가로와 세로의 길이를 구했다.

뭔가 보이지 않는가???

Yellow 가로 * 2 + Yellow 세로 * 2 = 주변의 Brown 개수와 같다!

그러면 공식은

(i + Yellow개수/i) * 2 == Brown - 4(주변뺌) 가 가능하다

i = 세로 개수
Yellow개수 / i = 가로 개수

이 공식에 적절한 가로, 세로를 구한다.

그 후, Yellow의 가로와 세로를 정확하게 구했으니 주변에 Brown이 둘러싸고 있으니 가로 + 2, 세로 + 2 하면 답이 나온다.

이걸 생각한 사람은 진짜 대단한 것 같다……… 존경

---

코드 방법 1

def solution(brown, yellow):
    for w in range(3, brown):
        for h in range(3, brown):
            if (w + h - 2) * 2 == brown and w*h-brown== yellow:
                return ([max(w,h), min(w,h)])

코드 방법 2

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