카펫
문제설명
Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.
Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.
Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.
제한사항
갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.
내 코드
def solution(brown, yellow):
sum = brown + yellow
for i in range (sum, 2, -1):
if sum % i == 0:
j = sum // i
if yellow == (i-2)*(j-2):
return [i,j]앞서 풀었던 문제는(프로그래머스_큰 수 만들기) 힌트를 얻기까지 오랜 시간이 걸려 해당 문제는 풀기전 설명되어 있는 힌트를 확인하고 문제를 풀었다.
해당문제는 완전탐색 알고리즘을 활용하여야한다.
문제를 풀기 앞서 완전탐색 알고리즘의 개념을 숙지해보았다.
완전탐색이란 모든 경우의 수를 다 체크하여 정답을 찾는 알고리즘이다.
완전탐색 알고리즘은 직관적이어서 이해하기 쉽고 문제의 정확한 결과값을 얻을 수 있는 가장 확실한 기초적인 방법이라고 한다.
그러나 해당 알고리즘을 이해하지 않아도 규칙을 찾아서 문제를 해결할 수 있었다.ㅠ ㅠ
예제 출력을 통해 규칙을 발견을 해보면 아래와 같다.(a = 가로, b = 세로)
1. 가로는 세로의 길이보다 크거나 같다.
a>=b
2. 노란색의 태두리 이므로 2변의 가로 길이 2변의 세로길이에서 중복되는 네점을 빼주면 brwon의 길이를 구할 수 있다.
2a+2b-4 = brown
3. 브라운의 가로 및 세로는 2만큼 작다는 특징을 활용하여 가로세로를 연산해주면 yellow의 길이를 구할 수 있다.
(a-2)(b-2) = yellow
4. 주어진 브라운 옐로우의 숫자를 더한 숫자는 구하려는 가로 세로 길이의 공배수이다.
