프로그래머스 : 카펫 (C++, Lv.2, 완전탐색)

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

코딩테스트 연습 - 카펫

 

격자의 가로가 세로보다 길거나 같다는 점을 이용해 탐색할 첫 가로의 길이를 격자 수의 제곱근의 천장함수로 잡아 완전탐색하였다.

 

 

소스코드

#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int length;

bool cmp(int a, int b) {return a > b;}

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    //전체 격자 개수
    int all = brown + yellow;
    //가로는 세로보다 크거나 같다는 점을 반영, -1은 반복문의 첫 문장 width++를 위해서 미리 하나 지워줌.
    int width = ceil(sqrt(yellow))-1;
    
    
    while(width <= yellow ) {
        width++;
        //약수가 아니면 다음 루프로 이동
        if(yellow%width !=0) continue;
        
        length = yellow / width;
        
        //전체 격자의 가로와 세로는 노란격자의 가로와 세로보다 2씩 크다는 성질을 이용해 격자 개수 비교하기
        if((width+2)*(length+2) == all) {
            answer.push_back(width+2);
            answer.push_back(length+2);
            break;
        }
    }
    return answer;
}