[Algorithm] 프로그래머스 카펫 C++

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

코딩테스트 연습 - 카펫

 

풀이

완전탐색 문제지만, 단순하게 연립방정식으로도 풀린다.

• 노란 카펫의 가로의 길이를 x, 세로의 길이를 y로 두면, 다음 두 식을 도출할 수 있다.
  • yellow = x \* y (노란 카펫의 개수를 x, y로 표현)
  • brown = 2(x + y) + 4 (갈색 카펫의 개수를 x, y로 표현)
• brown을 y에 대한 식으로 정리하고, 아래 그림의 과정을 거치면 x와 y를 구할 수 있다.
• 가로가 세로의 길이보다 같거나 크다고 했으므로, x와 y 중 큰 값을 먼저 출력한다.

 

수식 도출 과정

 

 

소스코드

#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    double x, y;
    int b = (4 - brown ) / 2;

    x = (-b + sqrt(pow(b ,2) - 4 * yellow)) / 2;
    y = (brown - 4) / 2 - x;

    answer.push_back(x+2);
    answer.push_back(y+2);
    sort(answer.rbegin(), answer.rend());

    return answer;
}