프로그래머스 카펫

red의 값을 소인수분해했을 때 가로와 세로를 각각 w, h라고 했을 때 빈 모서리를 채우는 4개와 2*w와 2*h를 합했을 때, brown의 개수와 같다면 답이 된다. 소인수분해를 할때는 루트 red까지 하는 것이 시간을 단축시킬 수 있다. 왜냐하면 두 곱을 a * b라고 표현한다면, 중복을 피한다는 가정 하에는 a의 최댓값은 루트 a이기 때문이다

 

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

깃허브주소: https://github.com/surinoel/boj/blob/master/Programmers_%EC%B9%B4%ED%8E%AB.cpp

 

	#include <string>
	#include <vector>
	using namespace std;
	vector<int> solution(int brown, int red) {
	vector<int> answer;
	int b, r;
	b = brown, r = red;
	for (int i = 1; i*i <= r; i++) {
	if (r%i == 0) {
	int h, w;
	h = i, w = r / i;
	if (b == 4 + h * 2 + w * 2) {
	answer.push_back(w + 2);
	answer.push_back(h + 2);
	return answer;
	}
	}
	}
	}

view raw Programmers_카펫.cpp hosted with ❤ by GitHub