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

#include <string>
#include <vector>
#include <cmath>
 
using namespace std;
 
vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    
    int tmp = (int)sqrt(yellow);
    int w,h;
    
    for(int i=1; i<=tmp; i++) {
        if(yellow % i == 0) {
            w = i;
            h = yellow / i;
            int b_tmp = w * 2 + h * 2 + 4;
            if(b_tmp == brown) {
                if(w > h) {
                    answer.push_back(w+2);
                    answer.push_back(h+2);
                }
                else {
                    answer.push_back(h+2);
                    answer.push_back(w+2);
                }
                break;
            }
        }
    }
    
    
    return answer;
}

문제 조건이 그닥 친절하지 않아서 애먹은 문제

 

1. 노란색 카펫은 무조건 사각형을 이룬다.

2. 노란색 카펫은 서로 떨어져있지 않다.

위와같은 두개의 조건이 추가되어야 하는데 누락됐다.

 

** 알고리즘

 

만약 yellow 가  12라고 가정하면 네가지 경우의 수가 생긴다

yy            yyyyyy       yyyy       yyy

yy            yyyyyy       yyyy       yyy

yy                               yyyy       yyy

yy                                              yyy

yy 

yy 

 

이제 갈색 카펫의 숫자를 추론해보자

 

O bb O

b  yy b

b  yy b     

b  yy b

b  yy b

b  yy b

b  yy b

O bb O

 

노란색 카펫의 가로 x2 + 세로 x2 + O 네칸 과 같은 공식이 설정된다.

 

위의 공식을 이용해 노란색 카펫의 가능한 모든 경우의 수를 탐색 해 갈색 카펫의 수와 같다면 결과 값으로 추가하면 된다.