[알고리즘문제] 프로그래머스 - 카펫



각각의 brown, red격자가 주어질 때, 만들 수 있는 카펫의 가로/세로 길이는 구하는 문제 입니다.

여기서 만들 수 있는 카펫이란 red의 격자가 중앙에 위치해 있는 경우이다.

 

사실 이 문제에 대한 설명이 조금 부족하다고 생각한다. 문제에서 "중앙"의 의미를 좀 더 구체적으로 예시를 들어 설명해주었으면 좋았을 것 같다는 생각이 들었다. 아무튼 나는 위의 사진처럼 좌/우의 gap이 같고, 상/하의 gap이 같은 경우를 중앙으로 생각하고 문제를 풀었다.

 

처음에 문제를 어떻게 풀 까 고민을 했었는데, 만들 수 있는 모든 red격자 모양을 만들면서 상/하/좌/우로 red격자를 덮었을 때 그 크기ㅏ brown보다 작거나 같은 경우를 찾았다. 

 

예를 들어, 입출력 예제3의 경우 red격자의 개수가 24개 이니깐, 만들 수 있는 모양의 조합은 [1,24], [2,12], [3,8], [4,6] 이렇게 된다.

만약 [4,6]의 red격자 를 만들었 다면(세로4, 가로6) red격자를 중앙에 위치하기 위해서는 세호6, 가로8의 크기를 가지는 brown격자가 필요하다. 

 

왜냐하면 red격자를 가운데 위치하기 위해서는 red격자에서 위/아래로 각각 1줄이 추가 되어야 하기 떄문이다.

----

xx

---   이런식으로 xx를 감싸야지 xx가 가운데 위치하게 된다. 이런 방법으로 좌/우에도 각각 1줄씩 추가하게 된다.

brown격자의 크기가 6,8이 되었고 넓이는 48이 된다. 근데 가운데 red격자가 있기 떄문에 이 격자의 넓이를 빼준 값이 입력으로 받은 brown과 작거나 같다면 그때의 brown의 가로/세로 크기를 return 하면 된다.

 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int red) {
    
    vector<int> answer;
    
    for(int i=1;i<=red;i++){
        if((red % i) == 0){
            
               int redWidth = red / i; // red격자 가로
               int redHeight = i;      // red격자 세로
               int redArea = redWidth * redHeight; // 만들어진 red크기
            
               int brownArea = ((redWidth+2) * (redHeight+2)); // 만들어진 brown크기
            
               if((brownArea-redArea) <= brown){ // 만들어진 brown에서 red크기를 뺸 값이 입력으로 받은 brown보다 작거나 같으면 return
                   answer.push_back(redWidth+2);
                   answer.push_back(redHeight+2);     
                   return answer;
               }
        }
    }
}