[프로그래머스/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 - 시간 복잡도:
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
Author And Source
이 문제에 관하여([프로그래머스/Python] 완전탐색 - 카펫), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sugenius77/프로그래머스Python-완전탐색-카펫저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)