[완전탐색, 난이도 중하] 프로그래머즈, 카펫

brown+yellow 개의 격자는 brown+yellow의 두 약수 n,m 의 곱으로 이루어질 수 있다.

이렇게 해서 가능한 두 약수의 조합들을 완전탐색하는 문제이다.

 

매개변수로 들어온 정수의 약수들을 모두vector에 담아서 그 vector을 리턴하는 함수를 추가로 만들었다.

 

두 약수를 n, m이라고 하자.

아래와 같이 n x m 카펫이 주어 졌을 때,

갈색 격자의 개수는 m*2+n*2-4 이다.

주어진 갈색 격자의 개수와 같게 나왔을 경우 m,n 값을 answer에 담아 리턴하면 된다.

테스트 케이스 13개 모두 통과

 

#include <vector>

using namespace std;
vector<int> get_prime_numbers(int n){
    vector<int> prime_numbers;
    for(int i=1;i<=n;i++){
        if(n%i==0) prime_numbers.push_back(i);
    }
    return prime_numbers;
}

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    vector<int> prime_numbers = get_prime_numbers(brown+yellow);
    int ps=prime_numbers.size();
    for(int i=0;i<ps;i++){
        if(prime_numbers[i]*2+prime_numbers[ps-i-1]*2-4==brown){
            answer.push_back(prime_numbers[ps-i-1]);
            answer.push_back(prime_numbers[i]);
            return answer;
        }
    }
    return answer;
}