[Python] 카펫 - 완전탐색

문제

해당 문제 링크

풀이

[ 풀이 1 ]

def solution(brown, yellow):
    
    for a in range(1, 2502):
        b=int(brown/2)+2-a

        if (a*b) ==(brown+yellow):
            answer=[b, a]
            break

    return answer

[ 풀이 2 ]

def solution(brown, yellow):
    a=[]
    x, y=0, 0
    for i in range(1, yellow+1):
        if yellow%i==0 :
            x=yellow//i
            y=i
            if x*2+y*2 +4 == brown: 
                a.append(x+2) 
                a.append(y+2)
                return sorted(a, reverse=1) 
    return a

결과

해석

처음 아래와 같이 코드를 작성하였다.

def solution(brown, yellow):
    
    res=brown+yellow
    a=[]
    
    for i in range(1, res+1):
        if(res%i==0):
            x=res//i
            a.append([i, x])
    
    n=len(a)

    return a[n//2]

하지만 아쉽게 테스트에 통과하지 못했다..
좀 더 고민했지만 더 이상 생각이 안들어 다른 사람의 코드를 참고하여 제일 이해가 쉽게 된 코드로 작성했다.

풀이 1

brown = ab-yellow = ab-(a-2)*(b-2) = ab-(ab-2a-2b+4) = 2a+2b-4 =2(a+b)-4
a+b = (brown-4)/2 = brown/w-2

yellow = (a-2) * (b-2) = ab-2a-2b+4
ab = yellow+2a+2b-4=yellow+2(a+b)-4 = yellow+brown

1<=yellow<=2,000,000
8<=brown<=5000 => 6<= a+b <=2502, b>=1 전제로
for문을 1부터 2501까지 순회한다!
b를 앞으로 쓴 이유는 a가 1부처 순회하기 때문에 더 작은 값이 나옴

---

풀이 2

각 한 줄씩 코드를 해석해보자면
노란색의 가로 세로를 이용하여 문제를 풀게된다. 그렇기 때문에 for문에서 yellow의 가로(x) 세로(y) 길이를 구하도록 돌아간다.

if yellow%i==0 :

이 코드는 약수로 나오게 하기 위해/ 나누어 떨어져지지 않는다면 x값이 안나온다.
예를 들면 yellow=24 / i=7일 경우이다.

각 노란색의 x, y 값을 구했다면,

x*2+y*2 +4 == brown

을 이용하여 계산한다
+4를 해준 이유는 각 모서리에 해당하는 격자의 갯수를 더해주기 위해서이다.
배열 a에 .append(x+2) 를 한다. x+2 하는 이유 또한 모서리에 있는 값을 포함한 것이 브라운 격자이기 때문이다.
마지막 반환할 때도 sorted 한 이유는 가로 길이가 더 크기 때문에 정렬을 내림차순으로 하여 맞는 결과를 반환하기 위해서이다.