프로그래머스 (Level 2) - 카펫

1. 문제 설명

• 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색, 테두리 1줄은 갈색으로 칠해져 있는 카펫을 발견했다.

• 집으로 돌아와서 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만 전체 카펫의 크기는 기억하지 못했다.
• 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개 변수로 주어진다.
• 이때, 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return하라

---

2. 제한사항

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

---

3. 입출력 예

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

• 갈색 10장, 노란색 2장이면 위 사진처럼 총 12장이다. 따라서 가로 4, 세로3이 나온다.
• 갈색 8장, 노란색 1장이면 총 9장이며 가로3, 세로3이 나온다.
• 갈색 24장, 노란색 24장이면 총 48장이며 가로8, 세로6이 나온다.

---

4. 풀이 접근

1. return되는 값, 즉 가로 * 세로 = brwon + yellow (총 타올의 수)이다.
2. 조건이 가로 >= 세로 이므로 이 조건에 맞는 가로, 세로를 구한다.
3. 총 타올의 수를 1 ~ 마지막 수까지 배열로 두고 접근한다.
   1. 총 타올의 수가 5이면 1-2-3-4-5 이렇게
4. 0번째를 i, 그뒤를 j로 두고 i * j = 총 타올의 수가 되는 모든 수를 구한다.
5. i는 j를 넘어가는 경우 종료하고 가장 i-j 차이가 적은 것을 선택한다.

---

5. 코드

def solution(brown, yellow):
    tot = brown + yellow
    
    x = []
    y = []
    array = [i+1 for i in range(tot)] #선언된 수 만큼 1부터 배열 초기화
    
    for i in range(tot):
        x_position = array[i]
        for j in range(i,tot):
            y_position = array[j]    
            if((x_position * y_position) == tot):
                x.append(i+1)
                y.append(j+1)
            
    min_num = y[0] - x[0]
    for i in range(len(x)):
        if(min_num > (y[i] - x[i])):
            min_num = y[i] - x[i]
            num = i

    x_su = y[num]
    y_su = x[num]
    
    return [x_su, y_su]

• 배열로 만들어 정렬로 접근했다. 하지만 매우 느려서 시간초과가 떠서 통과하지 못했다.

 

이렇게 풀면 더욱 간단해진다.

def solution(brown, yellow):
    size = brown + yellow
    for i in range(3, brown):
        if size % i == 0:
            j = size // i
            if (i - 2) * (j - 2) == yellow:
                return sorted([i, j], reverse=True)

혹은 근의 공식을 이용한다.

def solution(brown, yellow):  # 근의 공식 활용
    x = (brown + 4 + ((brown + 4) ** 2 - 16 * (brown + yellow)) ** 0.5) / 4
    y = (brown + yellow) / x

    return [x, y]

---