[완전 탐색]카펫

문제

 

• 문제 설명
  Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.
  
  
  
  Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만,
  전체 카펫의 크기는 기억하지 못했습니다.
  
  
  Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때
  카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.
  
  
  제한사항
  갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
  노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
  카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.
  입출력 예
  brown   yellow  return
  10  2   [4, 3]
  8   1   [3, 3]
  24  24  [8, 6]

 

접근법

 

1. 출력 값 정의
<카펫의 가로 세로 크기>

2. 문제의 해

<갈색이 밖, 노란색이 안에있는 경우의 수 찾기 >

1) 갈색은 가로 세로가 최소 3 이상.alignas
2) 노란색은 가로 세로가 갈색 가로,세로 -2.
3) 전체 수를 알 고있음.
4) 전체 수에서 width-2*length-2 의 값이 yellow인 경우 찾으면 됨.

=> 이거는 완전탐색이야 그리디야?
이것도 이 경우를 만족하는 경우의수를 모두 찾는거기때문에 완전탐색이지.

3. 구현
1) 타일 전체 합 구하기
2) 3부터 시작하여 width length 구하기
3) width-2*length-2의 값이 yellow와 동일한 경우 착지.
해당 경우 width와 length 배열을 리턴.

 

 

코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;

vector<int> solution(int brown,int yellow)
{
    int whole = brown + yellow;
    int width=3,length=3;
    vector<int> res;

    for(int i=3;i<=sqrt(whole);i++)
    {
        if(whole%i==0)
        {
            width = i;
            length = whole/i;

            if(((width-2)*(length-2))==yellow)
            {
                res.push_back(max(width,length));
                res.push_back(min(width,length));

                break;
            }
        }
    }

    return res;
}

 

 

추가 보완 사항

 

1) 반복문의 종료 조건 파악

 - 한 수의 약수 쌍을 계산할 때, 한 수의 파악 범위 최댓값은 수의 루트값이다.

 - 약수의 성질로 인하여 수의 루트값 초과되는 약수들은 이전 값들과 위치만 다르고 같은 값들의 쌍이기 때문이다.

 

 => 따라서 범위를 3<=i<=sqrt(whole)으로 설정해야 한다.