프그스_완전탐색_카펫_레벨2 (고득점 kit_수학)

• 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42842

---

메모한 것

테케를 봤을 때
brown + yellow = 넓이 = x * y 이렇게 되는 거잖아

밑변의 길이로 계산해보면 어떨까

ex) 브라운 10일 때

브라운 절반 나눠 = 두줄   || 밑변 5
ㅁㅁㅁㅁㅁ
ㅁㅁㅁㅁㅁ
-1 빼 = 네 줄됨   || 밑변 4
ㅁㅁㅁㅁ
ㅁ    ㅁ             
ㅁㅁㅁㅁ
   -> 이때 if 밑변 - 2(양끝) == 옐로우면 => return [밑변, 여태까지 -1한 횟수+2]
   
-1 빼 = 세 줄됨   || 밑변 3
ㅁㅁㅁ
ㅁ  ㅁ
ㅁ  ㅁ
ㅁㅁㅁ
-1 빼 = 두 줄됨   || 밑변 2
ㅁㅁ
ㅁㅁ
ㅁㅁ
ㅁㅁ
ㅁㅁ

ex) 브라운 12일 때 (중요)

x = 12
ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ,ㅁㅁ
ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ,ㅁㅁ

x = 11
ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ,ㅁ
ㅁ1 2  3 4 56 7 8 9  ㅁ
ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ,ㅁ

x = 10  "여기 중요"  --> depth만큼 수식에 곱해줘야함!!!
ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ
ㅁ910111213141516 ㅁ
ㅁ1 2  3 4 56 7 8 ㅁ 
ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ

---

솔루션 코드 - 내가 푼

• 처음에 보자마자 방법 생각이 안남
• 집가는 길에 수학적으로 생각했는데
• 특징 : 브라운은 무조건 짝수임, 정답의 옐로우는 무조건 1이상
• 알고리즘

1. 브라운을 반 자른다 => 반 자른게 밑변 시작이고, 이경우엔 옐로 못들어감
2. 밑변 -1씩 해준다 => 위아래로 -1씩한 ㅁ를 위 아래 변 사이에 붙여준다
   • 그러면 옐로가 들어갈 구멍이 가운데 생김
   • 그 구멍의 수 = yellow면 정답, yellow = (x - 2) * depth

def solution(brown, yellow):
    answer = []
    
    x = brown // 2
    cnt = 0
    
    for i in range(1, x+1):
        if (x - 2) * cnt == yellow:
            return [x, cnt + 2]
        else:
            cnt += 1                # yellow의 높이
            x -= 1                  # 밑변의 길이에 -1
            
print(solution(10,2))
print(solution(8,1))
print(solution(24,24))

---

솔루션 코드 - 다른사람

• 나처럼 수식 세워서 푼 사람들이 많은데 머리좋은 사람은 많다..(사람마다 공식 다름)
• 제일 깔끔하고 무서운(?) 사람은 이사람인듯
• 길이, 넓이 공식 각각으로 식 두개 만들고 변수 두개 존재하니까 이차방정식 -> 근의공식
• 완전탐색 방식은 아니다

import math
def solution(brown, yellow):
    w = ((brown+4)/2 + math.sqrt(((brown+4)/2)**2-4*(brown+yellow)))/2
    h = ((brown+4)/2 - math.sqrt(((brown+4)/2)**2-4*(brown+yellow)))/2
    return [w,h]