[프로그래머스] [C++] 위장 (brute-force)

1. 문제

코딩테스트 연습 - 카펫 | 프로그래머스 (programmers.co.kr)

 

2. 풀이 1

 

b + y  를  높이 1부터 시작하여 너비 를 차근 차근 구하는 풀이 이다.

 

이때 너비는 n 보다 작으며 높이로 나눠질 수 있어야한다.

 

#include <string>
#include <vector>
 
using namespace std;
 
vector<int> bf(int w, int h, const int& brown, const int& n) {
    int tmpBrown =  (h <= 2)? w*h: (w+h)*2 -4; 
    if(tmpBrown != brown) {
        for(int i = h+1; i <= n; i++)
            if(n % i == 0) 
                return bf(n/i , i, brown, n);
    }
    else
        return (h <= w)? vector<int>({w, h}): vector<int>({h, w});
}
 
vector<int> solution(int brown, int yellow) {
    return bf(brown + yellow, 1, brown, brown+yellow);
}

3. 풀이 2

 

이것은 기본 수학식으로 간단히 표현할 수 있다.

 

yellow 가 무조간 1개 이상이므로

 

항상 높이는 3이상이다.

 

그리고 갈색은 테두리이다.

 

wh = b + y

(w-2)(h -2) = y

wh - 2w - 2h + 4  = y

 

b - 2w - 2h + 4 = 0

 

w  = b/2 + 2 - h

 

최소 높이는 3 이므로

 w의 처음 걊은 b/2 -1 이 된다

 

w + h = b/2 + 2 으므로

(w + 1) + (h - 1) = b/2 + 2

가 성립한다.

그러므로 높이, 너비를 1씩 증가 , 감소 시킬 수 있는 것이다.

#include <string>
#include <vector>
 
using namespace std;
 
vector<int> bf(int w, int h, const int& n) {
    if(w * h != n) {
           return bf(w-1 , h+1, n);
    }
    else
        return (h <= w)? vector<int>({w, h}): vector<int>({h, w});
}
 
vector<int> solution(int brown, int yellow) {
    return bf(brown/2 -1, 3, brown+yellow);
}

 

 

 

코딩테스트 연습 - 카펫 | 프로그래머스 (programmers.co.kr)