프로그래머스 - 카펫

 코딩테스트 고득점 Kit 완전탐색 Level 2 카펫 문제이다. 이 문제는 완전 탐색으로 푸는 문제지만, 완전 탐색을 하는 기준이 중요한 문제이다. 처음에는 가로와 세로의 길이에 대한 완전 탐색으로 풀려고 했지만, 이는 최악의 경우 5000 * 2000000 = 100억번의 연산을 할 수도 있으므로 시간 초과가 난다. 그래서 yellow의 개수를 알고 있고, 이 안에서 가로 세로 길이를 정해놓으면 자연스럽게 brown의 개수도 나오므로 이를 통해 문제를 풀었다.

 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    
    for (int i = yellow; i >= 1; i--)
    {
        int width = i;
        int height = yellow / i;
        
        if (width * height == yellow && width >= height)
        {
            int tempBrown = (width + 2) * 2 + height * 2;
            
            if (tempBrown == brown)
            {
                answer.push_back(width + 2);
                answer.push_back(height + 2);
                break;
            }
        }
    }
    
    return answer;
}