[C++] 프로그래머스 카펫 완전탐색

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    
    for(int i = 6; i <= brown - 2; i+=2) //x가 가질 수 있는 최대범위 brown - 2까지
    {
        for(int j = 2; j <= brown / 2; j+=2) //y가 가질 수 있는 최대범위 brown / 2까지
        {
            if(i + j == brown && i / 2 >= (j / 2 + 2))
            {
                if((i / 2 - 2) * (j / 2) == yellow)
                {
                    answer.push_back(i / 2);
                    answer.push_back(j / 2 + 2);
                }
            }
        }
    }
    
    return answer;
}

 

풀이

1. 패턴을 잘 읽으면 쉽게 풀 수 있다.
2. x 는 6 * (i += 2) ...씩 늘어나고
3. y는 2 * (j += 2)... 씩 늘어난다.
   
   

x	x	x
y		y
x	x	x

이 상황을 기본으로 시작한다.

고로 가로의 길이는 i / 2 로 기준을 하였고

세로의 길이는 j / 2 + 2 인 것 이다.
 

  4. 세로의 범위가 가로보다 작거나 같아야된다.
  5. yellow의 개수는 (i / 2 - 2) * (j / 2)와 같아야 한다.

 

x, y	x	x	x, y
y	yellow	yellow	y
x, y	x	x	x, y

i가 8이고 j가 2일경우

i / 2 는 가로의 길이지만 그 안에 속해야되기 때문에

테두리 1씩 빼서 i / 2 - 2

y는 j가 2므로 j / 2만 하면 yellow의 높이가 된다.

 

결국 2 >= 1이고 2 * 1이 yellow와 같기 때문에 답이므로

answer에 x길이 (i / 2)와 y의 길이 (j / 2 + 2)를 넣어주면 정답이 나온다.