문제 설명 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. 제한사항 Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다. Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.
입출력 예
코드
def solution(brown, yellow):
answer = []
yellow_x = 0
yellow_y = 0
for i in range(1, yellow+1):
if yellow % i == 0:
yellow_x = yellow // i
yellow_y = i
if 2*yellow_x + 2*yellow_y + 4 == brown:
answer.append(yellow_x+2)
answer.append(yellow_y+2)
break
answer.sort(reverse = True)
return answer
다른 풀이
def solution(brown, yellow):
# 전체 타일의 개수
total = brown + yellow
# 가능한 세로 길이를 순회하며 조건을 만족하는 가로, 세로 찾기
for height in range(3, int(total ** 0.5) + 1):
if total % height != 0:
continue
width = total // height
# 가로 길이가 세로 길이보다 같거나 커야 함
if width < height:
continue
# yellow 영역이 맞는지 확인
# yellow = (width-2) * (height-2)
if (width-2) * (height-2) == yellow:
return [width, height]
return None # 해를 찾지 못한 경우
문제 풀이
카펫의 구조 파악
테두리 1줄은 brown
내부는 모두 yellow로 채워짐
카펫의 세로 길이를 h, 가로 길이를 w로 두고 계산
전체 타일의 개수 = w × h = brown + yellow
yellow area = (w-2) × (h-2) 테두리 한 줄은 brown 이므로 양옆에서 1씩 뺀 것.
w ≥ h
계산 순서
세로 길이는 최소 3부터 시작함 (테두리 brown 2줄 + yellow 최소 1줄)
전체 타일 개수(brown + yellow)를 세로 길이(h)로 나누어 가로 길이(w) 구하기
구한 w, h 길이로 yellow area 계산 -> 주어진 yellow 값과 일치하는가?
w < h 인 경우는 건너뛰기 (무조건 가로세로 길이 같거나 가로가 길어야 함)
모든 조건이 맞으면 그 w, h 길이를 정답으로 return
예시 테스트
주어진 brown=10, yellow=2
전체 타일 = 12개
if h=3 : w=4 이고, 내부의 yellow area: (4-2)*(3-2)=2 여서 주어진 yellow=2 값과 일치함
정답은 [4,3]
이런 방식으로 모든 경우의 수를 완전탐색하면서 모든 조건을 만족하는 해답을 출력하면 solve!
