[프로그래머스] 완전 탐색 - 카펫 c++

 

입출력 예)

Brown	Yellow	return
10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

Brown, Yellow를 매개변수로 입력 받았을 때 return값에 대한 규칙이 있다.

1) Brown + Yellow = x * y 식으로 표현할 수 있다.

2) Brown + Yellow 의 공약수를 중에

3) (x-2) * (y-2) == Yellow 를 만족하는 값이 return 값이다.

 

#include <string>
#include <vector>
#include <stack>   //stack
#include <cmath>   //sqrt : 제곱근을 구하는 함수

using namespace std;

vector<int> solution(int brown, int yellow) {
    
    //brown + yellow = x * y
    
    int sum = brown + yellow;
    
    int num = sqrt(sum)+1;  // ( sum / 2)를 사용 했을 경우 for문 검사수(index)가 증가하게 되어 속도를 높이기 위해
                           //제곱근을 사용. 
    stack<pair<int, int>> sCD;
      
    for(int i = 1; i < num; i++)
    {
        if(sum % i  == 0  )
        {
            int x = i;
            int y = sum / i;
            
            if( (x-2) * (y-2) == yellow)       //처음에는 (y -x < 4 ) 라고 대략적인 조건을 걸었다.
                sCD.push(make_pair(y , x));        //x와 y의 수 차이가 적은 값을 찾기 위해 조건을 고민해 보다가
                                          //다른 사람의 풀이 중에 ( (x-2) * (y-2) == yellow) 식을 보게 되서 적용하였다.
        }
                  
    }
     vector<int> answer;
    
    if(sCD.size() > 0)
    {
        answer.push_back(sCD.top().first);
        answer.push_back(sCD.top().second);
    }

    return answer;
}

 

이 문제를 보고 먼저 2가지 식을 도출해내야 한다.

1) Brown + Yellow = x * y

2) (x-2) * (y-2) == yellow