프로그래머스 - 카펫(완전탐색)

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 이하인 자연수이다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 길다.

 

# 입출력 예

brown	yellow	return
10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

 

# 풀이

- 위 그림과 같이 노란색의 가로, 세로가 항상 갈색의 가로, 세로보다 2가 작다.

- 우선 전체 넓이(size)를 구하고 1씩 줄이면서 가로의 길이(w)를 구한다.

- 가로의 길이가 구해지면 size를 나눠주어 세로의 길이(h)를 구하고, 주어진 조건식에 맞으면 답을 출력한다.

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

 

# 고찰

- 문제 해결 아이디어를 떠올리는 데 생각보다 오래걸렸다.

- 코드 구현도 중요하지만 문제를 어떻게 풀 것 인가에 대한 아이디어를 잘 떠올리는 연습이 필요할 것으로 보인다.

 

# 다른 풀이(약수를 이용)

- 노란색의 넓이의 약수를 구해서 그 약수를 이용하여 전체 가로와 세로의 넓이를 구할 수 있다.

- 탐색의 범위를 줄여 구현 시간이 많이 줄어드는 것을 확인할 수 있다.

import math

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