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

yunyoung·2021년 1월 20일
2

알고리즘

목록 보기
12/41

문제 설명

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

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

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

제한사항

  • 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
  • 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
  • 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

입출력 예

brownyellowreturn
102[4, 3]
81[3, 3]
2424[8, 6]

문제 풀이

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

노란색 부분의 가로 세로를 구하기 위해, yellow의 약수를 for문으로 구해준다. 이 때, 만약 yellow2라면 (1,2), (2,1) 이렇게 둘 다 구할 필요 없이 (1,2)만 구하면 되기 때문에 for문의 반복 범위를 제곱근까지만 지정해준다.

노란색 부분으로 갈색 테두리 격자 수를 구하는 식은 노란색 부분의 둘레 + 4로 나타낼 수 있다. 노란색 부분이 1*2라면, 2*(1+2)+4가 될 것이다.

계산한 값이 brown과 일치할 경우 전체 카펫의 가로 세로는 노란색 부분의 가로 세로 길이에 각각 2씩 더한 값이다. for문이 1부터 yellow의 제곱근까지 돌고 있기 때문에, i가 항상 작은 값이고 yellow/i가 항상 큰 값이 나온다.

소스 코드

profile
🌈TIL과 개발 노트

0개의 댓글