[코딩테스트 고득점 Kit / Level2 🧒🏻 / 완전탐색] 카펫(python)

1. 문제 설명

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

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

2. 제한 사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

3. 입출력 예

4. 나의 풀이

brown과 yellow의 개수를 더해서, 그것들의 약수들을 구한 후에, brown과 yellow개수를 더한 값이 곱셉으로 가능한 첫번째로 발견한 쌍이면 정답이다고 생각했다.

def solution(brown, yellow):
    answer = []
    numbers = list()
    numCarpet = brown + yellow
    for num in range(1, numCarpet +1):
        if (numCarpet) % num == 0:
            numbers.append(num)
    
    for num in numbers:
        if numCarpet//num in numbers and numCarpet//num <= num:
            answer = [num, numCarpet//num]
            return answer

그런데 이렇게 풀었더니 .. 테스트케이스는 충족시켰으나 테스트 4, 6, 7을 실패했다 ㅠㅠ

근데 나처럼 ,,, 4,6,7을 틀리는 분들이 많은 듯 했다.

질문목록을 찾아봤더니 answer = [x. y]라고 했을 때 (x-2)*(y-2) = yellow가 되어야 한다고 한다.

카펫 안쪽 넓이(yellow)는 (x-2)*(y-2) -> 가로, 세로 각각 겹치는 부분을 빼서 곱한다.

예를 들어, 입력값과 기댓값이 다음과 같을 때.

입력값 〉 14, 4
기댓값 〉 [6, 3]

ㄱㄱㄱㄱㄱㄱ
ㄱㅇㅇㅇㅇㄱ <- 이 경우로 해결해야 함
ㄱㄱㄱㄱㄱㄱ

 

ㄱㄱㄱㄱ
ㄱㅇㅇㄱ <- 이 경우는 통과 못함
ㄱㅇㅇㄱ
ㄱㄱㄱㄱ

즉, 조건을 정리하자면,

x * y = brown + yellow이며, (x-2)*(y-2) = yellow이다.

def solution(brown, yellow):
    answer = []
    numbers = list()
    numCarpet = brown + yellow
    for num in range(1, numCarpet +1):
        if (numCarpet) % num == 0:
            numbers.append(num)
    
    for num in numbers:
        if numCarpet//num in numbers and numCarpet//num <= num:
            answer = [num, numCarpet//num]
            if (num-2)*(numCarpet//num -2) == yellow:
                return answer

5. 다른 사람의 풀이

def solution(brown, yellow):
    for i in range(1, int(yellow**(1/2))+1):
        if yellow % i == 0:
            if 2*(i + yellow//i) == brown-4:
                return [yellow//i+2, i+2]

6. 깨달은점

- 그림문제가 나왔을 때 규칙이 무엇일까? 조건이 무엇일까?? 테스트케이스들을 그려보고 생각하면서 구해야겠다!