[Coding Test] 프로그래머스 - 카펫

https://programmers.co.kr/learn/courses/30/lessons/42842

코딩테스트 연습 - 카펫

 

[문제 설명]

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

 

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

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

 

[제한사항]

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.

• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.

• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

 

---

idea

- 주어진 변수(brown, yello)로 가로와 세로 블럭 개수에 대한 식을 세운다.

brown = 갈색 블럭의 수 = 노란색 블럭을 둘러싼 블럭의 수 = 가로 brown 블럭(W)과 세로 brown 블럭(H)의 합

yello = 노란색 블럭의 수

식 1)  brown = {(W+2) +(H+2)}*2 - 4 : 가로변의 블럭 수*2 + 세로변의 블럭 수*2 - 가로블럭과 세로 블럭이 겹치는 모서리 4개만큼 빼기

>> H+W=(brown+4)/2 -2로 고쳐 쓸 수 있다.

식 2) yellow = (H+2)*(W+2) : yellow 가로변에서 양쪽으로 2개 블럭씩 덧대면 H와 같음. 세로변도 마찬가지.

>> yellow를 (H+2)로 나누면 그 몫이 (W+2)이다. 마찬가지로  yellow를 (W+2)로 나누면 그 몫이 (H+2)이다.

위의 두 식을 통해 (H+2)와 yellow를 (H+2)으로 나눌 때 그 몫인 (W+2)을 합하고, 각각 2를 곱한 다음 4를 빼면 brown과 같아진 다는 것을 알 수 있다.

즉,  yellow/(H+2)=(W+2), brown = {yellow/(H+2)+(H+2)}*2-4

코드로 표현하면 아래와 같다.

def solution(brown, yellow):
    arr=[]
    for height in range(1,int(yellow**0.5)+1):
        if(height+(yellow//height)==(brown//2)-2):
            arr=[(yellow//height)+2,height+2] #가로변과 세로변 중첩되어 계산하므로 각각 2를 더함
    return arr