[프로그래머스/Python] 완전탐색 - 카펫

🤓 나의 풀이

• 노란색 격자의 가로 세로를 먼저 선택한 후, 테두리를 그려 그 테두리의 격자 수와 brown이 같은지 판단하는 방법으로 알고리즘을 구현

# 첫 번째
def solution(brown, yellow):
    answer = []
    for i in range(yellow,0,-1):
        if yellow % i == 0:
            if ((i + (yellow // i)) * 2) + 4 == brown:
                answer.append(i+2)            
    if len(answer) == 1: answer.append(answer[0])
    return answer

• 마지막 if len(answer)~~ 부분이 마음에 들지않는다..
  가로와 세로 길이가 같을 때 하나의 숫자만 들어가기 때문에 넣은 조건문..

import math
def solution(brown, yellow):
    answer = []
    # 24의 제곱근: 4.898979485566356
	# i는 4, 3, 2, 1
    for i in range(int(math.sqrt(yellow)),0,-1):
        if yellow % i == 0:
            if ((i + (yellow // i)) * 2) + 4 == brown:
                answer.append(yellow // i+2) 
                answer.append(i+2) 
    return answer

-math.sqrt(yellow) 힌트를 얻었슴니다.

✏️ 수학 공식

• 딩초 5학년 수학
  
  
• 갈색 테두리 격자의 수 = 노란색 부분의 둘레 + 4
  = { ( 노란색 가로 + 노란색 세로 ) x 2 } + 4

✏️ Python 문법

산술 연산자

math.sqrt()

• 약수 구할 때 사용하는 거 전혀 몰랐쥬?
  N의 약수를 구할 때는,
  1부터 N의 제곱근 까지의 수만 0으로 나누어 떨어지는지 확인하면 된다!"
• 왜?
  아래에서 100의 약수를 구하는 사례를 살펴보자.
  우리는 제곱근까지만 구하기로 했으니, 1 ~ 10 사이의 수에 대해서, 100이 0으로 나누어 떨어지는지 보면 된다.
  100 % 1 = 0
  100 % 2 = 0
  100 % 3 = 1
  100 % 4 = 0
  100 % 5 = 0
  100 % 6 = 4
  100 % 7 = 2
  100 % 8 = 4
  100 % 9 = 1
  100 % 10 = 0
  이를 통해서, 100의 약수는 일단 1, 2, 4, 5, 10 을 갖는다는 것을 알게 되었다.
  100에 이미 구해진 1, 2, 4, 5, 10을 나눈다
  100 / 1 = 100
  100 / 2 = 50
  100 / 4 = 25
  100 / 5 = 20
  100 / 10 = 10
  그렇게 되면, 이미 구했던 1, 2, 4, 5, 10 외에 100, 50, 25, 20, 10이 추가로 구해진 약수가 된다는 것을 알 수 있다.
  이제, 중복을 제거하고 오름차순으로 순서를 정렬하자.
  100의 약수: 1, 2, 4, 5, 10, 20, 25, 50, 100
• 시간 복잡도: $O(√N)$

import math
math.sqrt(36) # 0.6

# 또는
print(36 ** 0.5) # 0.6

출처
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=nexus128&logNo=221499461651
https://blog.naver.com/xowns4817/221086364812
https://m.blog.naver.com/heartflow89/221053732991
https://kbw1101.tistory.com/32