[프로그래머스] Lv2. 카펫 (파이썬) / 완전탐색

[문제 링크]

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

프로그래머스

[문제 고민]

• 1차 시도: 둘레로 접근해볼까? →  장렬히 실패
• 2차 시도: yellow 약수 조합에 따라 가로, 세로 길이는 무조건 yellow 카펫 + 2여야한다는 사실 발견. 다만, 세로의 경우 가로에 따라 영향 받음. (ex) brown: 8 , yellow: 1 → yellow 카펫이 1개이므로 brown 카펫은 "최소" 좌/우, 위/아래 총 4개 필요함. 따라서, 가로는 1+2 = 3 / 세로는 1+2 =3이다. (아래 그림 참고)
• 3차 시도: 넓이로 접근해봄. 위의 논리에 따라 yellow 카펫이 1개일 때 가능한 조합은 가로 3 , 세로 3 뿐이다. brown 개수의 경우 넓이(3*3) - yellow 카펫 개수 (1개) = 8개로 구할 수 있다는 점에서 이걸 조건으로 코드 구현.

좌/우, 위/아래가 필요한 이유..?

[핵심 개념]

1. 약수 조합 및 넓이의 관계..? 

 

[추가 끄적]

1. 둘레로 시도한다면 더 짧은 코드로 구현이 가능한 것 같다. 이 부분 확인이 필요하다.

 

[작성 코드]

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