[Programmers/C++] 카펫

시간 복잡도

• 노란색 격자가 최대 2,000,000 이고 인수는 $\sqrt{n}$ 까지 반복하여 구할 수 있습니다.
• 시간 복잡도는 $O(\sqrt{n})$ 으로 충분합니다.

문제 접근법

• 노란색 격자가 들어갈 수 있는 모든 크기, 즉 노란색 격자의 모든 인수를 구합니다.
• 해당 인수는 $n x m$의 노란색 격자가 만들어지고 해당 격자를 둘러싸는 갈색 격자의 개수와 비교합니다.
• 둘러싸는 갈색 격자의 개수가 동일하고 가로의 길이가 세로의 길이보다 크거나 같을 때가 정답입니다.

코드

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

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    
    for(int i=1; i<=sqrt(yellow); i++)
    {
        if(yellow%i==0)
        {
            int row = i+1;
            int col = (yellow/i)+1;
            
            if(col>=row)
            {
                if((row+col)*2 == brown)
                {
                    answer.push_back(col+1);
                    answer.push_back(row+1);
                    break;
                }
            }
        }
    }
    
    
    return answer;
}