프로그래머스 - 카펫 파이썬

0. 문제링크

가로, 세로를 구하라

1. 접근 

음... 하나하나 해보면서 다이나믹프로그래밍으로 규칙을 찾던가 

아니면 완전탐색일듯

시간복잡도를 보니까 

제한사항
갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.

완탐으로 풀어도 되겠다 

 

2. 어떤 알고리즘? 

완탐으로 풀다가 규칙성보이면 DP로 가자 

 

3. 해결 코드 

def solution(brown, yellow):
    # 가로(w)와 세로(h)의 초기값 설정
    w = (brown / 2) + 1  # 가로는 갈색 타일 개수를 2로 나누고 1을 더한 값
    h = 1  # 세로는 1로 초기화

    # 가로(w)가 세로(h) 이상일 때까지 반복
    while w >= h:
        # 현재 가로와 세로의 내부 영역을 계산하여 노란색 타일 개수와 비교
        if (w - 2) * (h - 2) == yellow:
            # 노란색 타일 개수가 일치하면 가로(w)와 세로(h) 값을 반환
            return [w, h]

        # 노란색 타일 개수가 일치하지 않으면 가로를 줄이고 세로를 늘림
        w -= 1
        h += 1