[프로그래머스/완전탐색] L2: 카펫 - 파이썬

문제

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

코딩테스트 연습 - 카펫

 

풀이

문제를 다 풀었지만 테스트케이스 4번에서 자꾸 오류가 났었는데

(이 사람도 나와 같은 문제를 겪었다. https://programmers.co.kr/questions/6882)

30분동안 헤메다가 답을 찾았다. (여기를 참조함 https://programmers.co.kr/questions/11500)

 

위와 같이 가로가 가장 큰 순서대로 정렬하여 가로가 가장 큰 값을 결과로 도출하면 된다.

(첫번째 출력은 노란색이 나올 수 있는 경우의 수, 두번째는 전체 크기(노란색+갈색)이 나올 수 있는 경우의 수

세번째는 조건을 만족하는 경우의 수 이다)

 

문제에 답에 대한 정확한 명시가 있었으면 하면 바램이다.

(다음 풀이는 best-case가 아니므로 이런식으로 풀이를 할 수 있구나 하고 참고하시면 되겠습니다.)

def solution(b, y):
    e = b + y # 노란색, 갈색 전체 합
    yList = []
    eList = []

	# 노란색 크기가 나올 수 있는 경우의 수 구해서 리스트에 저장
    for i in range(1,y+1):
        if y % i == 0:
            if i >= y//i:
                yList.append([i, y//i])

	# 노란색, 갈색 합친크기가 나올 수 있는 경우의 수 구해서 리스트에 저장
    # 문제에서 세로의 길이가 3 미만이면 노란색 부분은 나올 수 없음
    for j in range(3, e+1):
        if e % j == 0:
            if j >= e//j and e//j >=3:
                eList.append([j, e//j])
    
    # 결과를 저장할 리스트 선언
    result = []
    # 전체 크기의 경우의수가 저장된 리스트에서 노란색 크기가 나올 수 있는 경우의 수 구함
    for i in range(len(eList)):
        for j in range(len(yList)):
        	# 전체 크기 경우의 수 중에 한쪽 면이 노란색 크기의 면보다 -2가 되는지 확인해야함
            # 이를 만족하지 않으면 갈색 크기 안에 노란색 크기가 들어갈 수 없음
            if eList[i][0] >= yList[j][0]+2 and eList[i][1] >= yList[j][1]+2:
                result.append(eList[i])
    # 결과들 중 가로의 길이가 제일 긴 순서대로 정렬
    result.sort(reverse = True)
    # 맨 앞의 원소가 우리가 찾고자 하는 값
    answer = result[0]

    return answer

 

다른 풀이

수학적으로 접근하여 푸는 방법이 있다.

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

카펫 넓이 = brown + yellow = width * height

외부 사각형 갯수(brown) = 2w + 2h + 4

내부 사각형 갯수(yellow) = (x-2) * (y-2)