[프로그래머스] 카펫 c++

문제 링크

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

프로그래머스

 

코드 및 풀이

 

생각을 단순하게 변을 x,y라고 생각을 하고

2x + 2y - 4 =  갈색의 겉에 감싼 합

x * y = brown + yellow 라는 조건식을 충족한다면 맞는 것이니 return을 하였습니다.

 

근데 여기서 y값이 더 작거나 같다는 조건을 충족하기 위해 y를 큰 반복문으로 돌리고

또한 시간 절약을 위해 brown + yellow의 루트를 씌웠습니다

-> 약수 구할때 전체 반복문이 아닌 제곱근까지만 구하는 소수판별을 기억하시면 됩니다.

/*

노란색과 갈색으로 색칠된 격자의 갯수 기억 but 크기는 기억 x

중앙은 노란색 테두리는 갈색

추측 1)

가로 변 새로 변을 x,y라고 치면

네변의 갈색의 합은 2x + 2y - 4로 구성이 된다.

brown + yellow 의 갯수합은 xy이다. -> 이를 통해 약수여야 함

약수는 기본적으로 숫자 n이라 치면 루트n까지만 구하면 다 구해짐 -> 시간 절약

즉, 문제의 예시로 따지면 x의 값이 더 크니 약수를 구할때 36이면 6까지만 구하면 되는거임

*/

#include <string>

#include <vector>

#include <cmath>

using namespace std;

vector<int> solution(int brown, int yellow) {

    vector<int> answer;

   

    int c_sum = brown + yellow; //두개 타일의 합

    int n = int(sqrt(c_sum)) + 1; // 36이라면 6까지만 체크하면 됨

    int x_len = 0 ;

    int y_len = 0;

   

   

    for(int y = 1; y < n ; y ++){

        int x = 1;

        while (1){

            if (brown == 2*x+2*y-4 && x*y == c_sum){

                //조건 가로길이는 세로길이와 같거나 새로길이보다 김 -> 나중에 xy추출하고 큰거를 앞으로 하면 됨

                answer.push_back(x);

                answer.push_back(y);

                return answer;

            }

            if(x * y > c_sum){

                break;

            }

            x++;

        }

    }

   

    return answer;

}