[프로그래머스] 카펫

https://programmers.co.kr/learn/courses/30/lessons/42842?language=swift# 

코딩테스트 연습 - 카펫

카펫의 테두리 개수와 전체 - 테두리 개수를 알 때, 직사각형의 크기를 구하는 문제이다.

[프로그래머스] 카펫

예를 들어 brown = 10, yellow = 2이 주어졌을 때, [4x3] 이라고 출력할 수 있어야 한다.

(조건. 가로의 길이가 세로의 길이보다 크거나 같다.)

문제는 완전 탐색이지만, 수학적으로 접근해볼 수 있을 것 같았다.

즉 테두리에서 모서리 부분은 무조건 정해져있고, 주어진 조건식을 이용한 방정식을 통해 해를 구할 수 있을 것 같았다.

갑자기 수학 시간... 같지만 한 번 봐보자.

우선 정의를 해보자.

w = 가로

h = 세로

b = 테두리(갈색)

y = 중앙(노랑)

$$2(w-2)+2(h-2)=b-4......(1)$$

모서리 부분을 제외한 가로와 세로를 각 2개씩 더해주면 테두리 - 4와 같아진다.

$$(w-2)\times(h-2)=y......(2)$$

또한 모서리 부분을 제외한 가로와 세로를 곱하면 노란색 블럭의 개수와 같아진다.
이 두 식을 가지고 해를 구할 수 있다.

우선 w-2를 W, h-2를 H로 치환해보자. (-2를 달고 다니기는 귀찮으니...)

1번 식을 풀어보면 다음과 같이 정리할 수 있다.

$$2y+2H^2=H(b-4)$$

이 식을 대전제로 깔고 그 다음으로 충족해야 하는 조건을 깔면 답을 구할 수 있다.

다음으로 중요하게 봐야할 조건들은 다음과 같다.

$$W \neq 0 \ or \ H \neq 0 $$
$$ W \geq H$$
$$W \times H = b + y$$

간단하게 생각해보면 직사각형의 정의(?)를 따르는 것과 같다.

이제 식이 아닌 코드로 표현해보자.

import Foundation

func solution(_ brown:Int, _ yellow:Int) -> [Int] {
    // 편의상 소문자로 표기
    // 등식에서 W = w, H = h
    // 나중에 +2씩 해줌으로써 같게 해준다. 
    var w = 0
    var h = 0

    // h 범위 제한 
    for n in 0..<brown / 2 {
        // (1)번식 정리
        if (2 * yellow + 2 * n * n == n * (brown - 4)) {
            h = n
        }

        // 조건 1번
        if h != 0 || w != 0 {
            w = Int(ceil(Double(yellow / h)))
            // 조건 2번과 3번
            if w >= h && ((2 + w) * (2 + h) == brown + yellow) {
                w += 2
                h += 2
                break
            }   
        }   
    }

    return [w,h]
}

식을 그대로 코드로 옮긴 것이어서, 식을 이해했다면 크게 어렵지 않을 것이다.
이렇게 공식으로 규정이 된다면, 이런 방식으로 접근해보는 것도 하나의 방식이 될 수 있을 것 같다.