<Programmers> Brute Force_카펫 Carpet c++

Google 아니고 Joogle·2021년 12월 13일
0

Programmers

목록 보기
5/22
post-thumbnail
  1. yellow 카펫의 가로를 y, 세로를 x 라고 두었을 때, brown 카펫의 가로는 y+2, 세로는 x+2 이다. brown 카펫의 개수는 (y+2)(x+2) - (yx) 이다.
  1. yellow 카펫의 가로, 세로의 쌍을 구해주면 된다
    y*x=yellow 가 되는 값을 구해주면 되므로 yellow의 약수를 구해주면 된다.
vector<int> findAliquot(int y_num) {
    vector<int> v;
   
    v.push_back(1);
    if (y_num<4)
        v.push_back(y_num);
  
    for (int i=2; i<=y_num/2; i++) {
        if (y_num%i==0) {
            v.push_back(i);
            v.push_back(y_num/i);
        }
    }
   
    sort(v.begin(), v.end());
    return v;
}

주어진 y_num이 4보다 작으면 약수는 1과 자기 자신 뿐이다
y의 값을 구하면 x의 값은 바로 구할 수 있으므로 for문을 y_num의 절반만큼만 돌린다.

3. 전체 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> findAliquot(int y_num) {
    vector<int> v;
    
    v.push_back(1);
    if (y_num<4)
        v.push_back(y_num);
    
    for (int i=2; i<=y_num/2; i++) {
        if (y_num%i==0) {
            v.push_back(i);
            v.push_back(y_num/i);
        }
    }
    
    sort(v.begin(), v.end());
    return v;
}

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    
    vector<int> v=findAliquot(yellow);
    
    int vSize=v.size();
    
    for (int i=0; i<=vSize/2; i++) {
        int x=v[i]+2;
        int y=v[vSize-(i+1)]+2;
        
        if (y*x-yellow==brown) {
            answer.push_back(y);
            answer.push_back(x);
            break;
        }
    }
    
    return answer;
}

profile
Backend 개발자 지망생

0개의 댓글