프로그래머스 : 카펫

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42842

프로그래머스

 

 문제 설명  

 

카펫의 가장자리의 갯수와 안쪽 의 갯수가 각각주어질때 카펫의 사이즈를 return 하면됨. 

 

 알고리즘

 

1. 가장자리의 갯수와 안쪽 갯수를 더하여 넓이를 구함.

    3번예제) 24 + 24 = 48

 

2. 넒이를 통해 가능한 카펫 사이즈 경우의 수를 추려냄 

    3번예제  ) 넓이 : 48 -> (가로 :12 ,세로 4), (가로 :8 ,세로 6) , (가로 :16 ,세로 3)

    여기서 세로의 길이는 3이상이여야함 세로의 길이가 2이면 빨간색의 격자수는 0이므로 불가능.

 

3. 경우의 수를 이용해 레드카펫 사이즈 를 유추 가능 .

     (가로 :12 ,세로 4) -> 레드 카펫 사이즈 (가로 10,세로 2): 넓이 20

     (가로 : 8 ,세로 6)  -> 레드 카펫 사이즈 (가로 6,세로 4) : 넓이 24   -> 이경우가 답이겠네.

     (가로 : 16 ,세로 3)  -> 레드 카펫 사이즈 (가로 14,세로 1) : 넓이 14

 

4. (3) 번을 이용해 카펫의 사이즈 return.

 

 

 코드 

 

#include<iostream>
#include <string>
#include <vector>
#include<math.h>
using namespace std;
 
vector<int> solution(int brown, int red) {
    vector<int> answer;
    int sum = brown + red;
    int garo, sero;
    //i의 최소값은 3이고 최대값은 sqrt(sum)이다.( 약수의 최대값 )
    for (int i = 3; i <= sqrt(sum); i++) {
        //i가 sum의 약수이면
        if (sum % i == 0) {
            garo = i;
            sero = sum / i;
            if ((garo - 2) * (sero - 2) == red) {  // 레드카펫 의 넓이와 같으면
                answer.push_back(sero);
                answer.push_back(garo);
            }
        }
 
    }
 
    return answer;
}
h