[프로그래머스] 레벨 2 - 카펫

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

코딩테스트 연습 - 카펫 | 프로그래머스

프로그래머스 완전탐색 문제다.

DFS나 BFS, 비트마스킹, next_permutation 사용한 건 아니고

규칙을 찾는 문제였다.

 

나같은 경우 가장 바깥 갈색 영역의 가로의 길이를 W, 세로의 길이를 H로 지정하고,

내부에 있는 빨간색 부분의 가로의 길이를 w, 세로의 길이를 h로 지정했다.

 

그리고 전체 카펫의 넓이의 반부터 W를 내려가면서 H와의 조합을 찾은 뒤,

마찬가지 방법으로 빨간색 넓이의 반 부터 w를 내려가면서 h와 조합을 찾고

W와 w, H와 h크기를 비교한 뒤, 위아래, 양옆의 간격이 짝수인지 확인해서 빨간색 부분이 가운데에 있는 것을 확인했다.

#include <string>
#include <vector>
 
using namespace std;
int W, H, w, h;
vector<int> solution(int brown, int red) {
    bool out = false;
    vector<int> answer;
    int total = brown + red;
    for(W = total/2; W>=1; W--){
        if(total % W == 0){
            H = total / W;
            for(w = red; w >= 1; w--){
                if(red % w == 0){
                    h = red / w;
                    if(W > w && H > h){
                        if(((W-w) % 2) == 0 && ((H-h) % 2) == 0){
                            answer.push_back(W);
                            answer.push_back(H);
                            out = true;
                            break;
                        }
                    }
                }
            }
            if(out) break;
        }
    }
    return answer;
}