본문 바로가기

알고리즘/알고리즘 문제

[python] 프로그래머스 > 완전탐색 > 카펫

<문제>

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

 

코딩테스트 연습 - 카펫

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

programmers.co.kr

1. 문제 설명

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

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

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

 

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]

 

 

<내가 푼 방법>

from numpy import median

def solution(brown, yellow):
    answer = []
    # yellow의 약수 구하기
    yak_list = [int(i) for i in range(1, yellow+1) if yellow % i == 0]
    
    # 약수의 갯수가 짝수 일 경우
    if len(yak_list) % 2 == 0:
        while len(yak_list):
            x = yak_list.pop()
            y = yak_list.pop(0)
            if (x+2)*(y+2)-(x*y) == brown:
                answer.append(int(x+2))
                answer.append(int(y+2))
                return answer
    # 약수의 갯수가 홀수 일 경우
    else:
        while len(yak_list):
            if len(yak_list) == 1:
                x = median(yak_list)
                y = x
            else:
                x = yak_list.pop()
                y = yak_list.pop(0)
            if (x+2)*(y+2)-(x*y) == brown:
                answer.append(int(x+2))
                answer.append(int(y+2))
                return answer

 

 

<다른사람이 푼 방법들>

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]

 

def solution(brown, red):
    nm = brown + red
    for n in range(1, nm+1):
        if nm%n != 0:
            continue
        m = nm//n
        if (n-2)*(m-2) == red:
            return sorted([n, m], reverse = True)

 

import math
def solution(brown, yellow):
    w = ((brown+4)/2 + math.sqrt(((brown+4)/2)**2-4*(brown+yellow)))/2
    h = ((brown+4)/2 - math.sqrt(((brown+4)/2)**2-4*(brown+yellow)))/2
    return [w,h]

 

def solution(brown, red):
    answer = []
    cand_w = 3
    cand_h = 3
    total_blocks = brown + red
    for w in range(3, total_blocks):
        for h in range(3, total_blocks):
            if w * h < total_blocks:
                continue
            elif w * h > total_blocks:
                break
            elif w < h:
                break
            else:
                if 2*w + 2*h - 4 == brown and w*h - 2*h - 2*w + 4 == red:
                    answer.append(w)
                    answer.append(h)
                    break
        if len(answer) != 0:
            break

    return answer