카펫(Level2)

• 문제 링크: 코딩테스트 연습 > 완전탐색 > 카펫

• 문제 이해
  1. 주어진 두종류의 격자 수를 통해 카펫 크기를 예상합니다.
  2. yellow 격자를 brown 격자가 감싸는 형태의 카펫을 만듭니다.

• 알고리즘 구현
  1. yellow 격자를 brown 격자가 감싸기 때문에, 먼저 yellow 격자 형태를 정합니다.
  2. 직사각형 모양의 카펫을 만들기 때문에, yellow 격자를 직사각형 배열로 만듭니다.
  3. 이를 위해, 주어진 yellow 격자 개수의 약수를 구합니다.
  4. yellow 격자들이 이루는 직사각형을 둘러싸는 직사각형은, 2x가로 + 2x세로 + 4개의
  격자를 갖게 되므로, 이와 brown 격자의 수가 같으면 정답입니다.

• 알고리즘

#include <string>
#include <vector>

using namespace std;

#include <iostream>
void makeCapet(int brown, int yellow, vector<int> &grid) {
    int width;
    int height;
    for (int i = 1; i <= yellow; ++i) {
        // 약수가 아니라면 넘기기
        if (yellow % i != 0) continue;
        width = i;
        height = yellow / width;
        if (brown == 2 * width + 2 * height + 4) {
            grid[0] = height + 2;
            grid[1] = width + 2;
            break ;
        }
    }
}

vector<int> solution(int brown, int yellow) {
    vector<int> answer(2);
    makeCapet(brown, yellow, answer);
    return answer;
}