[프로그래머스-레벨2]카펫 - python

iamjinseo·2022년 9월 26일

완전탐색 프로그래머스

문제풀이-Python

목록 보기

104/134

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

문제 설명
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]

풀이

# 갈색은 노랑의 확장이다. 갈색을 두르고 나면 노랑가로+2, 노랑세로+2   만큼의 카펫이 생성된다.
def solution(brown, yellow):
    div = [] # 약수
    
    #약수찾기 (노랑격자의 가능한 가로, 세로 길이)
    for i in range(1, int(yellow**(0.5))+1):
        if yellow % i == 0 :
            div.append([i, yellow//i])
            div.append([yellow//i, i])

    size = set()
    # 노랑격자에서 확장한 후의 카펫 사이즈가 size와 동일한가?
    for w, h in div : 
        if (w+2)*(h+2) == yellow + brown and w>=h :# return 숫자의 곱하기는 brown+yellow. 즉, 실제사이즈
            # 조건 : 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.
            size.add((w+2, h+2))
    return list(size)[0]

카펫은 결국 노랑에서 가로+2, 세로+2 한만큼의 크기이다
그렇다면 입력에서 주어진 노랑의 약수는 가능한 가로, 세로이다
가로세로 크기 후보군에서 2씩 더한 후 서로 곱한 것이 진짜 사이즈(brown+yellow : 주석참고)
또한 제한조건에서 가로가 세로보다 크다고 했다.

결과

남의 코드

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