프로그래머스 문제 - 카펫

프로그래머스 카펫 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

중앙에 노란색 직사각형으로 카펫이 칠해져있으며, 나머지는 갈색으로 칠해져있습니다.
카펫의 노란색과 갈색으로 색칠된 격자의 개수가 주어집니다.
이때, 전체 카펫의 가로 세로를 구해야합니다.

문제 풀이

일단 전체 카펫의 크기는 노란색과 갈색으로 색칠된 격자의 개수를 전부 더한 값이 됩니다.
전체 카펫의 가로 세로를 구해야 하기 때문에, 가운데에 노란 카펫이 존재하기 위한 최소 높이 3인 직사각형 카펫으로 시작하여 카펫 중앙에 직사각형 모양의 노란색 카펫을 주어진 개수만큼 넣을 수 있는지 확인해줍니다.
카펫의 가로 길이는 세로 길이와 같거나 길다는 것을 유의하여 완전탐색을 진행하면 알맞는 카펫의 크기를 찾을 수 있게 됩니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    
    int height = 3;
    int width = (brown + yellow) / height;
    
    //노란색과 갈색을 더한 크기와 같으며, 노란색 격자 수만큼 직사각형이 가능한 카펫 크기 체크
    while(width >= height)
    {
        if(width * height != brown + yellow)
        {
            height++;
            width = (brown + yellow) / height;
            continue;
        }
        int w, h;
        w = width-1;
        h = height-1;
        
        while(w > 0 || h > 0)
        {
            if(w * h == yellow)
            {
                answer.push_back(width);
                answer.push_back(height);
                break;
            }
            w--;
            h--;
        }
        if(answer.size() != 0)
        {
            break;
        }
        height++;
        width = (brown + yellow) / height;
    }
    
    return answer;
}

출저

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