[programmers] 완전탐색, 카펫

코딩테스트 연습 - 카펫 | 프로그래머스

문제

Leo가 본 카펫에서 갈색 격자의 수 brown, 빨간색 격자의 수 red가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 빨간색 격자의 수 red는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

해결

key point, 1. 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.
               2. 모든 가능한 너비와 높이는 모든 격자 수의 제곱근까지만 탐색하면 구할 수 있습니다.

1. 갈색 격자 수와 빨간색 격자의 수를 모두 더하면 전체 격자 수가 됩니다. → total
2. 모든 격자 수에 대해서 가능한 너비와 높이 크기를 구해서 배열에 저장합니다. → width, height
   이때 카펫의 가로 길이는 세로 길이와 같거나 크므로, 크거나 같을 때 width배열에 추가합니다.
3. 모든 가능한 너비와 높이는 모든 격자 수의 제곱근까지만 탐색하면 구할 수 있습니다.
4. 너비와 높이를 모두 구했다면 해당 너비와 높이에 대해서 brown과 red값이 일치하는지 확인합니다.
5. 확인하여 맞다면 answer배열에 추가하고 종료합니다. 

코드

#include <iostream>
#include <vector>
using namespace std;
 
vector<int> solution(int brown, int red) {
    vector<int> answer;
    vector<int> width, height;
    int total = brown + red;
    for (int i = 1; i <= sqrt(total); i++) {
        if (!(total % i)) {
            int tmp = total / i;
            if (i >= tmp) {
                width.push_back(i);
                height.push_back(tmp);
            }
            else {
                width.push_back(tmp);
                height.push_back(i);
            }
        }
    }
    
    for(int i = 0; i < width.size(); i++) {
        int w =width[i], h = height[i];
        if ((w * 2 + (h - 2) * 2) == brown && (w - 2) * (h - 2) == red) {
            answer.push_back(w);
            answer.push_back(h);
            break;
        }        
    }
    return answer;