프로그래머스_카펫

https://programmers.co.kr/learn/courses/30/lessons/42842

코딩테스트 연습 - 카펫

 

• 접근법

카펫의 테두리 : 갈색(brown), 카펫 테두리를 제외한 내부 : 노란색(yellow)

갈색과 노란색의 값이 주어질 때 전체 카펫의 가로, 세로 길이를 구하는 문제이다.

완전탐색으로 풀 수 있는 문제지만 좀 더 수학적으로 풀어봤다.

def set_divisor(num) :
    divisor = []
    for i in range(1,num+1) :
        if num % i == 0 :
            divisor.append(i)
    return divisor

def solution(brown, yellow):
    divisor = set_divisor(brown + yellow)
    for i in range(len(divisor) // 2 + 1) :
        x = divisor[i]
        y = (brown+yellow) // x
        if 2 * (x + y - 2) == brown :
            answer = sorted([x,y], reverse=True)
            break
    return answer

 

• 코드 풀이

카펫의 가로길이 : x, 세로길이 : y 라고 했을 때

갈색의 수 = xy - (x-2)(y-2)가 된다 (전체 개수 - 내부 개수)

직사각형 격자의 총 개수는 가로*세로이므로 총 개수의 약수의 짝이 그 직사각형의 가로, 세로가 된다

문제에서 갈색의 개수, 노란색의 개수가 주어지므로 두 수를 더한 합의 약수를 구해

세로와 가로의 경우를 모두 구하여 위에서 구한 식 xy - (x-2)(y-2) 에 대입하고 이 식을 풀면 2(x+y-2)이다.

고로 위식의 결과값이 갈색의 값과 같다면 그 식에서 이용된 x,y가 카펫의 가로, 세로가 된다.