[c++] 프로그래머스 :: 카펫 (brute force)

 

카펫

코드

#include <string>
#include <vector>
#include <cmath>

using namespace std;


vector<int> solution(int brown, int yellow) {
    vector<int> answer;

    vector<pair<int, int>> candidate;

    for (int i = 1; i <= sqrt(yellow); i++) { // 10^3
        int x = i;
        int flag = yellow % x;
        if (flag == 0) {
            int y = yellow / x;
            candidate.push_back(make_pair(x, y));
        }
    }

    int size = candidate.size();
    for (int i = 0; i < size; i++) {
        int x = candidate[i].first; int y = candidate[i].second;
        int tmp = 2 * x + 2 * y + 4;
        if (tmp == brown) {
            answer.push_back(y+2);
            answer.push_back(x+2);
            return answer;
        }
    }

}

알고리즘 설명

1. yellow의 가로, 세로 후보를 구한다.

   1~sqrt(yellow) 까지 가면서 yellow가 해당 수와 나누어떨어지는 지 본다. 나누어 떨어지면 해당 수를 세로로 두고 나누는 수를 가로로 둔 후, 후보 vector에 저장한다.

2. 후보들을 하나씩 꺼내보며 brown과 맞는지 확인한다.

   => 맞으면 (가로, 세로) 길이를 결과 vector에 넣어서 return

   brown 갯수 = 2*가로yellow + 2*세로yellow +4

   4 : 양쪽 모서리

다른 사람의 코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int red) {

    int len = brown / 2 + 2;

    int w = len - 3;
    int h = 3;

    while(w >= h){
        if(w * h == (brown + red)) break;

        w--;
        h++;
    }

    return vector<int>{w, h};
}

yellow의 세로 길이를 1로 시작해서 늘려가는 동시에 가로 길이를 줄여가면서 조건을 충족하는지 확인하는 방식