[ 프로그래머스 ] 카펫

문제

---

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

풀이

---

노란색 격자가 가운데에 존재하고, 갈색 격자가 그 주위를 감싸고 있을 때, 해당 격자의 합은 카펫의 크기이다. 먼저 노란색 격자가 이룰 수 있는 사각형의 최소 인자를 구하고, 이를 통해 사각형을 이루었을 때, 주위에 배치되는 갈색 격자가 조건에 충족할 수 있는지 확인하고 이를 return한다. 다만, 조건으로 ‘카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.’라는 조건이 붙으므로, 내림차순 정렬을 진행 후 return한다.

#include <string>
#include <vector>
#include <functional>
#include<cmath>

using namespace std;

vector<int> solution(int brown, int yellow)
{
    vector<int> answer;
    vector<int> minFactor;

    // brown + yellow 가 사각형의 갯수
    // 가로와 세로를 곱하면 사각형의 갯수
    int sum = brown + yellow;

    for (int i = 1; i <= sqrt(yellow); i++)
    {
        if (yellow % i == 0)
        {
            minFactor.push_back(i);
            if (i != yellow / i)
            {
                minFactor.push_back(yellow / i);
            }
        }
    }


    for (int i = 0; i < minFactor.size(); i += 2)
    {
        if (minFactor[i] * minFactor[i] == yellow)
        {
            if ((minFactor[i] + 2) * (minFactor[i] + 2) == sum)
            {
                answer.push_back(minFactor[i] + 2);
                answer.push_back(minFactor[i] + 2);
                i++;
            }
        }

        // yellow의 (약수+2) * (약수+2) == result;
        if ((minFactor[i] + 2) * (minFactor[i + 1] + 2) == sum)
        {
            answer.push_back(minFactor[i] + 2);
            answer.push_back(minFactor[i+1] + 2);
            sort(answer.begin(), answer.end(), greater<int>());
        }
    }
    return answer;
}