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

문제 : 카펫

문제 설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다

 분석

노란색 부분이 카펫의 중앙인 것을 기반으로 규칙을 찾으면 다음과 같다.

 1. (노란색 가로 +2) * (노란색 세로 +2) = 카펫 (가로 * 세로)

 2. 갈색 = 2*(노란색 가로 + 노란색 세로) + 4

노란색의 가로, 세로 길이는 노란색의 약수로 구하면 된다.

 

 구현

using namespace std;

vector<int> solution(int brown, int yellow)
{
	vector<int> answer;
	vector<pair<int, int>> measures;
	
	// yellow의 약수 계산.
	int i = 1;
	for (i = 1; i*i < yellow; i++)
	{
		if (yellow%i == 0)
		{
			measures.push_back(make_pair(yellow / i, i));
		}
	}
	if (i*i == yellow) measures.push_back(make_pair(i, i)); // 제곱수인 경우

	// 가로, 세로 계산
	for (size_t i = 0; i < measures.size(); i++)
	{
		if (brown == 2 * (measures[i].first + measures[i].second) + 4)
		{
			answer.push_back(measures[i].first + 2);
			answer.push_back(measures[i].second + 2);
			break;
		}
	}

	return answer;
}

int main()
{
	vector<int> ans;
	ans = solution(10, 2);
	cout << ans[0] << ' ' << ans[1];
}