[완전탐색] 중학교 수학으로 빠르게 코딩하기

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

프로그래머스

 

 

 

문제를 다 읽었을 때 떠오른 2가지 방법론

 

1. yellow의 가로와 세로는, 무조건 전체 사각형의 가로 - 2 , 세로 - 2이다.

   그리고 당연히 그 yellow의 가로x세로는 yellow 넓이이다.

 

2. 전체 brown block의 절반은, 전체 사각형 (가로 -1 ) + (세로 -1)

즉, 가로+세로-2이다.

 

문제가 어차피 완전탐색(그냥 싹 다 구해보는 거)이고, 최대 블록수가 2,005,000 <= 2억 이기 때문에

그냥 바로 코딩으로 돌입했다.

 

def solution(brown, yellow):
    total = brown + yellow
    answer = []
    for i in range(3, total):
        if total%i != 0:
            continue
        height = i
        width = total / i
        if height+width-2 == brown/2:
        #if (height - 2) * (width - 2) == yellow:으로 대체해도 문제없다.
            answer.append(int(width))
            answer.append(height)
            break
    return answer

 

전체 블록수 (=전체 넓이)에 대해서 될  수 있는 가로 세로 중에서, (for문으로 i가 3일때부터 구했다, 어차피 yellow존재하려면 최소 가로세로의 길이는 3이니까)

 

위의 1번 혹은 2번을 만족한다면, 그것들을 return.

 

가로>=세로가 문제조건인데, for문에서 i가 작은값부터 시작해서 탐색하므로,

i가 세로, total/i가 가로라면 sort를 따로 안해도 된다.