[Algorithm🧬] 카펫

문제 / 풀이.py

나의 정답

import math

def solution(brown, yellow):
    answer = []
    j = 1

    for i in range(1, int(math.sqrt(yellow)) + 1):
        if yellow % i == 0: # yellow 의 약수에
        	# 포스팅하면서 생각해보니 이렇게 yellow 의 예상 가로 세로를 주고
            row = i
            col = yellow / i # 어차피 약수니까 정수가 나옴.
            while row * col < brown + yellow:
            	# 계속 2를 더하는 게 더 깔끔한 코드이면서 같은 결과가 나왔을듯.
                # 수정 이전 코드는 풀이.py 참고!
                row += 2
                col += 2
                
            if row * col == brown + yellow:
                return [row, col] if row > col else [col, row]
    
    return answer

문제

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

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.
Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

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

입출력 예

brown	yellow	return
10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

일단 처음에 이 문제를 보고 들었던 생각은

첫번째 case 를 예시로하면

brown + yellow 를 해서 카펫의 전체 크기를 알아내고 (12)

12 의 약수가 전체 카펫의 가로 세로가 될 수 있고,
색칠된 부분은 상하좌우로 한칸 혹은 두칸 혹은 세칸 ... 이렇게 차이가 날 테니까 그걸 다 계산해보면 되지 않을까? 였다.

(1, 12)
(2, 6)
(3, 4)

근데 약수가 많아서 비효율적일 것 같아서 반대로 생각했다.

색칠된 부분의 약수를 구하고 거기에 상하좌우 한칸, 두칸, 세칸 ... 을 더해서
예상 카펫의 가로 세로 길이를 구하고 곱해서 넓이가 맞는지 (== brown + yellow) 인지 확인해 보는 것.

1. (1, 2) -> (3, 4) = 12 정답!
2. (1, 1) -> (3, 3) = 9 정답!
3. (1, 24) -> (3, 26) = 78 > 48 안됨.. 더 커져봤자 넓이를 초과하기만 하므로 여기서 끝.
   (2, 12) -> (4, 14) = 56 > 48 X
   (3, 8) -> (5, 10) = 50 > 48 X
   (4, 6) -> (6, 8) = 48 정답!

그래서 먼저 약수를 구하기 위한 for 문 (효율성을 위해 root n 까지만 돌도록) 에서
약수일 때, 위처럼 가로 세로에 2씩 (상하좌우가 각각 1씩 늘어나니 가로 세로는 2씩 늘어남) 계속 더해보고 맞는 넓이가 나오는지 확인해보는 것. 말이 안되는 입력이 들어오면 [] 를 내보내기 때문에... 걱정했지만, 이상한 입력은 없었다.

import math

def solution(brown, yellow):
    answer = []
    j = 1

    for i in range(1, int(math.sqrt(yellow)) + 1):
        if yellow % i == 0: # yellow 의 약수에
        	# 포스팅하면서 생각해보니 이렇게 yellow 의 예상 가로 세로를 주고
            row = i
            col = yellow / i
            while row * col < brown + yellow:
            	# 계속 2를 더하는 것도 같은 결과가 나왔을듯.
                row += 2
                col += 2
                
            if row * col == brown + yellow:
                return [row, col] if row > col else [col, row]
    
    return answer