[프로그래머스 고득점 kit] 완전탐색 #3_카펫

(문제 설명)

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

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

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

제한사항

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

입출력 예brownyellowreturn

10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

---

( 문제 해설 )

 

위의 그림같이 노란색 카펫을 감싸는 형태의 갈색 카펫을 함께 깝니다. 그리고 갈색 카펫과 노란색 카펫의 개수가 주어 질 때 전체 카펫의 행, 열을 리턴을 해주는 문제입니다. + 가로의 크기가 더커야 합니다

노란색 격자수가 2,000,000인걸로보아 최적화도 혹시? 신경 써야 하나 생각이 듭니다.

 

사실 이문제는 수학문제 풀듯이 풀면 그나마 해결할 수 있습니다.

# 짚고 넘어가기

갈색 카펫의 행, 열의 -2씩 한 값은 노란색 카펫의 크기이다

즉, 갈색 카펫의 가로를 x, 세로를 y라고 할 때 노란색 카펫의 가로, 세로는 각각 x - 2, y - 2

 

# 생각 알고리즘

0. 카펫 하나 하나를 넓이라고 생각하면 넓이는 곧 카펫의 수라는 것을 인지해야 풀이의 이해가 쉬울 수 있습니다.

1. 노란색 카펫과 + 갈색 카펫의 수를 더합니다

2. 전체 카펫의 수가 // 갈색 카펫이 나눈 값이 나머지가 0이라면 그 값은 가로의 값(x),  세로의 크기는 자동으로 남은 몫 값이 세로(y)의 크기가 됩니다.

3. (x - 2) * (y - 2) 즉 노란색 카펫이라고 예상되는 가로 * 세로 = (넓이) 값이 주어진 yellow 카펫의 수이고

4. 가로의 크기가 세로크기보다 크다는 게 만족된다.

5. x, y는 우리 찾는 가로(x), 세로(y)의 크기 값이 됩니다. 이를 리턴하면 답은 끝납니다

6. 아니라면 x 값을 바꿔보면서 탐색합니다

 

---

[ 코드 ]

 

def solution(brown, yellow):
    answer = []
    total = brown + yellow
    # x: 행 y: 열
    for x in range(2, total):
        if total % x == 0:
            y = total // x
            if (x - 2) * (y - 2) == yellow and x >= y:
                return [x, y]
    return answer

---

후기

 

개인적으로 좋아하지는 문제 유형

수학문제 같은 느낌이 나서 재미는 있을 수 있으나

코딩 문제를 통해 코드를 설계하는 능력이 기르는 느낌은 들지 않는다.

단, 생각하는 연습이라는 마음으로 문제를 풀어보았다.