👓 문제 설명
Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.
Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.
Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.
입출력 예
brown yellow return 10 2 [4, 3] 8 1 [3, 3] 24 24 [8, 6]
💣 제한 사항
- 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
- 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
- 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.
🚨 접근 방법
갈색 격자는 항상 카펫의 테두리를 감싸고 있다.
그렇다면 세로 길이와 가로 길이를 가능한 경우의 수에 대해 모두 탐색해야한다.
하지만 세로는 최소 3 이상이 되어야 가운데 노란색 격자가 들어갈 수가 있다.
현재 세로와 가로에 대해 갈색 격자의 수를 구한 후 주어진 격자의 수와 일치하다면 정답으로 판단한다.
🚈 코드
#include <string>
#include <vector>
#include <iostream>
using namespace std;
vector<int> solution(int brown, int yellow) {
vector<int> answer;
// 1. 세로 길이 x, 가로 길이 y라고 하면 x*y = brown+yellow (넓이)
int total=brown+yellow;
// 2. x,y 쌍을 모두 찾기
for(int i=1;i<=total/2;i++){
if(total%i!=0)continue;
// 2-1. 불가능한 쌍 제외하기
int temp_x=i;
int temp_y=total/temp_x;
if(temp_x<3) continue;
// 3. 이 쌍을 통해 노란색 격자의 수 유추해서 확인하기
int temp_brown=(2*temp_y)+2*(temp_x-2);
if(temp_brown==brown){
answer.push_back(temp_y);
answer.push_back(temp_x);
break;
}
}
return answer;
}