[Programmers] carpet.py (complete search)

#. Problem

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

* The copyright in this matter is in Programmers

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 빨간색으로 칠해져 있고

모서리는 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 빨간색과 갈색으로 색칠된 격자의 개수는 기억했지만, 

전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 빨간색 격자의 수 red가 매개변수로 주어질 때

카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

    - 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.

    - 빨간색 격자의 수 red는 1 이상 2,000,000 이하인 자연수입니다.

    - 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

  3. Create solution plan (select Algorithm, Data structure)

    - complete search

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. brown + red는 총 격자의 개수이므로, s

     곱으로 총 격자의 개수를 만들 수 있는 두 수를 구해야 한다.

     brown + red = width* height

     단, "가로 >= 세로" 조건을 만족해야 한다. 조건으로 경우의 수가 조금 줄긴 할듯하다. 

     조건에 만족하는 두 수의 조합을 우선 list에 담아준다.

     여기서 (가로x2) + (세로-2)x2 = brown 을 만족하는 조합을 찾아주면 된다.

     왜 이러한 공식이 나오는지는 그림을 그려가면서 보면 편할 듯 하다.

#. Code

def solution(brown, red):
    answer = []
    area = brown + red
    for height in range(3, area):
        for width in range(height, brown):
            if width * height == area:
                if (width*2) + (height-2)*2 == brown:
                    answer.append([width, height])
                    break
    return answer[0]

  - 이중 반복문을 사용한 완전 탐색이다보니 계속 시간 초과가 발생하여 범위를 최대한 줄여주었다.

    height는 사실상 중간에 width가 구해지면 break하면 되므로 범위는 상관없지만,

    width는 범위 조절이 필요하다고 생각했다. 먼저 width는 무조건 height보다 크거나 같아야 하므로 초기값을 height으로 두었고

,   최댓값은 width가 아무리 커도 brown보다는 작을터이니 brown까지로 두었다.

#. Others code

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

  - (2) 1부터 red 개수의 제곱근 +1 까지 반복

    (3~5) red의 개수가 i와 나누어진다면,

           2*(i + red//i) == brown-4 조건이 만족한다면

           가로 : red//i+2, 세로 i+2 를 return

    * 나름의 규칙을 발견하여 적용한 코드같은데, 대단하다.. 

      로직은 말로 설명하기는 어렵고 그림을 그려보면서 보면 이해가 되는데

      어떻게 이런 규칙을 발견할 수 있는지 더 노력해야겠다는 생각 뿐..

def solution(brown, red):
    nm = brown + red
    for n in range(1, nm+1):
        if nm%n != 0:
            continue
        m = nm//n
        if (n-2)*(m-2) == red:
            return sorted([n, m], reverse = True)

  - n : 가로, m : 세로 라고 했을 때, 카펫의 너비는 nm

    (3) 1부터 너비만큼 반복

    (4~6) 너비가 n(가로)로 나누어지지 않는다면 continue

           나누어진다면 너비를 n(가로)으로 나눈 후 m(세로)을 구해준다.

    (7~8) 가로, 세로 길이에서 각각 2을 빼준 후 곱하면 red의 크기가 나온다. 

           이게 일치할 경우 가로값이 더 커야하므로 내림차순으로 정렬 후 return

    * 굉장히 참신하게 푼 것 같다.. 나도 조금만 더 생각했으면 이렇게 풀 수 있었을까?

      반복문도 한 번만 사용해서 정말 효율적인 코드인것 같다.