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

✅ LV. 2

🔖 완전탐색

✏️ 1차 솔루션

brown 개수를 기준으로 사각형 w, h 유추하기
1. 꼭짓점에 각 1개씩 들어가기 필요하기 때문에 brown - 4 부터 시작
2. 네 변에 동일하게 블럭을 배분하기 위해 (brown - 4) / 4 개가 각 변에 배치
3. 가로는 세로보다 더 길 수 있기 때문에 2 번 과정의 나머지를 가로에 배분해 (brown - 4) / 4 / 2 개 배치

🚨 1차 trouble

일부 test case 실패ㅜㅠ
1차 솔루션으로 사각형의 형태를 확정지을 수 있는 경우도 있지만 다양한 형태가 나올 수 있는 경우 존재
예를 들어 5*5 정사각형도 될 수 있지만 4*6 직사각형도 될 수 있는 경우가 그렇다!

✏️ 2차 솔루션

brown 값 기준만으로 하는 것이 아니라 brown 값으로 특정 지을 수 있는 형태에서 yellow 값도 정확히 떨어지는지 확인이 필요
1차 솔루션의 1~3 에 이어서
4. w*h 값이 yellow 개수와 동일한지 비교하고 동일하지 않다면 w 값을 늘려주고 h 값을 줄이면서 같을 때까지 수정해서 최종적인 w, h 확정하기

✏️ 최종 코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    
    int h=(brown-4)/4;
    int w=h+(brown-4)%4/2;
    
    while(1) {
        if(w*h==yellow) break;
        w+=1;
        h-=1;
    }
    
    answer.push_back(w+2);
    answer.push_back(h+2);
    
    
    return answer;
}