완전 탐색하기가 필요할 때

1. 문제

 

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

코딩테스트 연습 - 카펫

 

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

 

 

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만,

 

전체 카펫의 크기는 기억하지 못했습니다

 

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때

 

카펫의 가로, 세로 크기를 순서대로 배열에 담아 return하도록 solution함수를 작성해주세요

 

 

2. 제한사항

 

갈색 격자의 수 brown은 8이상 5000이하의 자연수

 

노란색 격자의 수 yellow는 1이상 2000000이하인 자연수

 

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

 

 

3. 입출력 예시

 

입출력 예시도 하나의 힌트가 될 수도 있어서 주목해야한다

 

 

4. 나의 풀이

 

입출력 예시를 보면 brown과 yellow의 합이 가로 세로의 곱임을 알 수 있다

 

머리로 생각해봐도 가로 세로의 곱인 면적이 타일의 총 수인 brown과 yellow의 합으로 구해진다는 것을 알 수 있다

 

제한 사항중에 가로 길이가 세로 길이보다 길거나 같다

 

def solution(brown, yellow):
    
    answer = []
    
    product = brown + yellow
    
    for v in range(1,product+1):
        
        h = product/v

 

for문을 돌면서 1부터 brown+yellow까지 세로의 길이를 검색한다

 

세로의 길이로부터 가로의 길이는 brown+yellow를 세로의 길이로 나누어 구한다

 

여기서 isinstance를 이용해서 h가 int인지 아닌지 검사할려고 했는데

 

h=product/v가 float로 나온다는거

 

그림1. 왼쪽이 h, 오른쪽이 v

 

h=product//v로 하면 몫을 구해주니까 의미가 없어.. 2.4는 2가 되어서 문제가 생기는거고

 

그래서 바꿔서 생각해보니까 int(h)랑 h가 같으면 int(h)를 h로 다시 저장하는 방법이 생각났다

 

 

 

이 조건에 맞으면 가로의 길이가 세로의 길이보다 길거나 같은지 검사하고

 

마지막으로 yellow의 배치는 애매한감이 있는데 brown은 확정적으로 테두리에만 배치하므로

 

가로의길이 2배에 세로의길이 2배를 합하고 모서리 4개를 빼면 brown의 수와 같으므로...

 

방정식을 세워서 brown과 맞는지 안맞는지 검사하는걸 추가

 

def solution(brown, yellow):
    
    answer = []
    
    product = brown + yellow
    
    for v in range(1,product+1):
        
        h = product/v
        
        if int(h) == h:
            
            h = int(h)
            
            if h < v:
                
                continue
            
            else:
            
                if brown == 2*h + 2*v - 4:
                    
                    answer.append(h)
                    answer.append(v)
                    
                    return answer
                    
            else:
                
                continue

 

 

5. 되돌아보기

 

다른 사람들 해법 살펴보니까 brown == 2*h+2*v-4가 핵심 아이디어같다..

 

+ brown과 yellow의 합이 가로 세로의 곱과 같다

 

이런 문제 보면 무슨 알고리즘 생각해야하나? 카펫보니까 저걸 그림으로 나타내는 class를 구현해야하나? 어렵게만 생각했는데

 

단순한 수학 방정식이 핵심 아이디어라니…

 

자신감 가져도 되겠는데? 

 

그 외에 정수인지 아닌지 검사하는 방법으로 isinstance도 있지만 int(h)와 h가 같은지 검사하는 방법도 자주 쓰인다