카펫의 크기 구하기 - 완전 탐색

카펫의 전체 크기를 출력

 

갈색과 빨간색으로 이루어진 격자 모양의 카펫이 있다.

갈색의 개수와 빨간색의 개수가 주어졌을 때 카펫의 전체 크기를 맞추는 문제이다. 빨간색은 갈색으로 둘러 쌓여있는 구조이다. 빨간색을 갈색으로 둘러 쌓으려면 위/아래, 좌/우로 한줄씩 더 나와야 한다는 사실을 알 수 있다.

 

빨간색의 개수가 주어졌을 때 약수끼리의 곱(a*b)으로 표현 할 수 있다. 이 때 약수끼리의 곱을 행과 열의 길이로 대입해서 풀면 된다. 약수를 구하는 방식은 완전 탐색으로 0으로 나누어 떨어지는 숫자를 구하면 된다.

최적화를 하면 완전 탐색으로 자기 자신의 숫자까지 오는게 아니라 제곱근까지 오면 된다.

 

위에서 찾은 약수끼리의 곱으로 a행과 b열로 구성 되었을 때 둘러 쌓을 수 있는 최소 숫자를 구한 후 매개변수로 주어진 갈색의 숫자와 일치하는지 검사하면 된다.

둘러 쌓을 수 있는 최소 숫자 = (열*2) + (행+2)*2

 

vector<int> solution(int brown, int red) {
    vector<int> answer;
    
    // 두 수의 곱으로 숫자를 표현 할 수 있다면 제곱근까지만 검사해도 된다.
    for(int i = 1; i <= sqrt(red); ++i)
    {
        if(red % i == 0)
        {
            int col = red / i;
            int row = i;
            int newBrown = (col*2) + (row+2)*2;
            
            if(newBrown == brown)
            {
                answer.push_back(col+2);
                answer.push_back(row+2);
                break;
            }
        }
    }
    
    return answer;
}