99클럽 코테 스터디 21일차 TIL / 완전탐색

✏️ 문제

[프로그래머스/Programmers] 카펫(https://school.programmers.co.kr/learn/courses/30/lessons/42842)

 

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

 

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다. Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

제한사항

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

 

🤖 입출력 예시

 

🧐 난이도/소요 시간

✅ 난이도: 프로그래머스 Level.2

✅ 소요 시간: 22분

✅ 권장 시간: 1시간 15분

 

💡 풀이

1) 문제 이해

전체 격자 수가 주어졌을 때 width*height = brown+yellow 이면서 (width-2)*(height-2) = yellow인 width 값, height 값을 찾으면 된다.

 

(width-2)*(height-2) = yellow 을 고려하지 않으면 문제에서 주어진 조건과 다른 그림이 나오게 된다.

 

예를 들어 brown = 18, yellow = 6 일 때 width가 height 이상이고 width*height가 brown+yellow 면 반복문을 탈출한다고 가정해보자. 여기서 (width-2)*(height-2) = yellow 조건이 없을 경우 width = 6, height = 4에서 반복문을 빠져나오게 되는데, 이 값을 가지고 갈색 격자가 노란색 격자를 둘러싸는 그림을 그려보면 brown = 16, yellow = 8 이어야 하는 걸 확인할 수 있다. 주어진 brown, yellow 값과 다르기 때문에 [6, 4]는 오답이다.

 

2) 아이디어 흐름

① i: 1부터 max(brown, yellow)까지 반복

 

② j: (brown+yellow)//i

 

③ i >= j 이고 i*j == total 이면서 (i-2)*(j-2) == yellow 이면 반복문 탈출

 

3) 구현

def solution(brown, yellow):
    total = brown+yellow
    
    width, height = 0, 0
    
    for i in range(1, max(brown, yellow)):
        j = total//i
        
        if i >= j and i*j == total:
            if (i-2)*(j-2) == yellow:
                width = i
                height = j
                break
            
    return [width, height]

 

4) 어려웠던 점/배운 점

🚨 어려웠던 점

• 없음

❗ 배운 점

• 숨어 있는 조건을 잘 생각해내야 한다.