[프로그래머스/Lv2] 카펫

 

 

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

프로그래머스

 

 

 

다른 사람들은 어떻게 저리 간단하고,, 멋진 방법으로 해결할 수 있을까..

개쩐다.. 저는 한참 남았군요... 

 

저는 약수를 사용해서 풀었습니다.

전체 카펫과 yellow 카펫의 약수를 구했습니다. 카펫은 직사각형으로 이루어지기 때문에 전체 카펫의 h, w는 전체 수의 약수들로 구성됩니다. 그래서 맞는 전체 카펫의 약수 짝꿍과 yellow 카펫의 약수 짝꿍을 완전 탐색으로 찾았습니다. 

약수를 찾을 때 for문으로 간단하게 할 수 있는데 여기서 9의 약수는 1, 3, 9로 나옵니다. 이렇게 되면 3의 짝꿍이 없습니다. 그러므로 그냥 i*i=t라면 i를 한번 더 넣어줍니다. (전 i는 앞에서 넣어줬죠)

이렇게 하고 solution 함수에서 2중 for문으로 짝꿍이 맞는 애를 찾아줍니다.

노란 카펫이 중앙에 있어야 하므로 일단 이 노란 카펫의 h, w보다 2 크거나 같아야 합니다. 그래야 중앙에 들어올 수 있죠.

맞으면 바로 answer에 w부터(가로 먼저 출력) 넣어주고 끝냅니다.

 

 

#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<int> divisor;
vector<int> yy;

void Divisor(int t, bool tt){
    if(tt){
        for(int i=1; i<=t; i++){
            if(t%i == 0) {
                divisor.push_back(i);
                if(i*i == t) divisor.push_back(i); //한번 더 넣기
            }
        }
        sort(divisor.begin(), divisor.end());
    }else{
        for(int i=1; i<=t; i++){
            if(t%i == 0) {
                yy.push_back(i);
                if(i*i == t) yy.push_back(i); //한번 더 넣기 (3*3==9인 경우)
            }
        }
        sort(yy.begin(), yy.end());
    }
}

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    int tt = brown + yellow;
    Divisor(tt, true);
    Divisor(yellow, false);
    
    for(int i=0; i<divisor.size()/2; i++){
        int h = divisor[i];
        int w = divisor[divisor.size()-1-i];
        if(h <= 2 || w <= 2) continue; //이건 가운데에 들어갈 수 있는게 없음
        
        for(int j=0; j<yy.size()/2; j++){
            int yh = yy[j];
            int yw = yy[yy.size()-j-1];
            if((yh+2 <= h && yw+2 <= w) || (yh+2 <= w && yw+2 <= h)) {
                answer.push_back(w);
                answer.push_back(h);
                return answer;
            }
        }
    }
    return answer;
}