개요

프로그래머스 : 카펫

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

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

접근 방식

1. 처음 보자마자 떠올린 생각은 yellow가 핵심이라는 것이다.
   yellow를 직사각형형태로 구성하면 테두리인 brown의 갯수는
   yello테두리의 갯수 *2 + 4로 정해진다.

2. 따라서 yellow를 완전탐색을 통해 나올수 있는 직사각형 형태로 구현 후, 해당 yellow의 테두리의 격자 갯수 *2 +4 값이 brown갯수와 같다면 답이 나온다.

3. yellow를 직사각형 형태로 구현하기 위해선 yellow의 약수를 구해야한다.
   이 부분은 [저번에 푼 에라토스테네스의 체]를 응용해서 제곱수가
   yellow를 넘어가지 않는 값까지 반복문을 돌려 약수들을 구하면 효율적이다.

      int width=0, height=0;
      for(int i=1;i*i<=yellow;i++){
          if(yellow%i!=0) continue;
   		width=i;
          height=yellow/i;

   주의할 점은 yellow값이 i로 나눠떨어지지 않는다면 continue를 해야한다.
   continue를 안한다면 yellow가 24일때,
   width가 5로 잡히면 height는 그대로 4가 잡혀서 yellow넓이가 안 맞는다.
   

4. 그 후, yellow 테두리 갯수 * 2 + 4가 brown갯수인지 확인한다.

   if(width*2 + height*2 + 4 == brown){
             if(width>height){
                 answer.push_back(width+2);
                 answer.push_back(height+2);
             }
             else{
                 answer.push_back(height+2);
                 answer.push_back(width+2);
             }
             break;
         }

   width가 height보다 크거나 같아야하므로 비교해서 넣어준다.
   찾았다면 break를 걸어줘 빠져나간다.

전체 코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    int width=0, height=0;
    for(int i=1;i*i<=yellow;i++){
        //yellow가 i로 안나눠떨어지면 continue해야함
        if(yellow%i!=0) continue;
        width=i;
        height=yellow/i;
        if(width*2 + height*2 + 4 == brown){
            if(width>height){
                answer.push_back(width+2);
                answer.push_back(height+2);
            }
            else{
                answer.push_back(height+2);
                answer.push_back(width+2);
            }
            break;
        }
        
    }
    return answer;
}

문풀후생

다른 사람의 풀이

다 풀고 다른사람의 풀이를 보던 중, 수학적으로 접근한 풀이를 보고 놀라웠다.
근의 공식을 이용한 풀이였다.

brown테두리의 가로길이를 x라고 하자.
brown테두리의 세로 길이는 brown/2+2 -x이다.
왜 +2를 해주냐면 brown을 2로 나누게 되면 꼭지점 두개가 빠진다.
우린 가로세로 갯수의 합이 필요하므로 2를 더해야한다.

이렇게 가로 x, 세로 brown/2+2 -x를 구했고 넓이는 brown+yellow이므로,
2차방정식이 나온다.
x * (brown/2 +2 -x)=brown+yellow;
x^2 - (brown/2 +2)x + brown+yellow=0;
근의 공식 사용시,
1/2* ((brown/2+2) - sqrt((brown/2+2)*(brown/2+2) - 4(brown+yellow))) 이렇게 된다.
이게 x값이고, y값은 brown/2 -x +2에 x값을 넣어주면 나온다.

코드

#include <vector>
#include <cmath>
using namespace std;

vector<int> solution(int brown, int yellow) {
    int x, y;  
    x= 0.5*((2+brown/2)+sqrt((2+brown/2)*(2+brown/2)-4*brown-4*yellow));
    y=  0.5*brown-x+2;
    return {x,y};
}