[프로그래머스] Level2 | 카펫 - 파이썬(Python) | 완전탐색

https://programmers.co.kr/learn/courses/30/lessons/42842?language=python3 

코딩테스트 연습 - 카펫

프로그래머스 완전 탐색 레벨2 문제 중 카펫을 풀었다.

---

문제에서 노란색 격자가 무조건 직사각형이어야 한다는 걸 명시해 줬으면 조금은 쉽게 풀지 않았을까 했다...

이 문제는 https://blog.naver.com/yh1313_/222079784715 해당 링크를 참고해서 풀었다.

해당 링크를 보고 이렇게 쉽게 풀수 있다는 걸 알게 되었다..

나는 무슨.. 갈색이랑 노란색이랑 곱한 것들의 약수를 구해서 그거가지고 어떻게 해보려고 했는데 잘 안됐다...ㅎ

 

아무튼.. 이 문제는 위의 링크에도 나와있지만 노란색의 가로 세로 칸 수를 이용하면 된다.

결국 구해야 하는 문제는 노란색의 가로 길이 +2, 노란색의 세로 길이 +2인 것이다.

이걸 어떻게 구하느냐? (yellow의 가로*2) + (yellow의 세로*2) + 4 이 값이 갈색 격자 수와 같으면 된다.

어떻게 저런 수식을 떠올릴까.. 너무 .. 너무 신기하다... 아무리 머리를 굴려도 노랑과 갈색 사이의 관계를 수식으로 표현할 수 없었는데... 

 

정답 풀이 코드

def solution(brown, yellow):
    
    answer = []
    
    yellow_x = 0
    yellow_y = 0
    
    for i in range(1, yellow+1) :
        if yellow % i == 0 :
            yellow_x = int(yellow/i)
            yellow_y = i
            if yellow_x*2 + yellow_y*2 + 4 == brown :            
                answer.append(yellow_x+2)
                answer.append(yellow_y+2)
                
                return sorted(answer, reverse = True)
    
    return answer

노란 격자의 가로(yellow_x)와 세로(yellow_y)를 이용해서 위와 같은 코드로 해결할 수 있다.

1부터 노란색의 개수만큼 for문으로 반복하면서 노란색의 수가 i로 나누어 떨어지면 노란색의 가로는 노란색을 i로 나눈 몫이되고, i는 노란색의 세로가 된다.

이때 위에서 언급한 수식을 사용하여 answer 리스트에 yellow_x+2와 yellow_y+2를 넣어준다.

가로가 세로보다 크거나 같아야 하기 때문에 내림차순으로 정렬을 한 리스트가 반환되도록 했다.

 

---

해당 문제 풀이 코드

GitHub - YOOHYOJEONG/algorithm_practice: 알고리즘 공부 및 코딩테스트 준비