[알고리즘] 프로그래머스 - 카펫 (완전탐색)

1. 문제

2. 풀이

중앙은 노란색으로 칠해져 있고, 나머지는 갈색으로 칠해져 있는 직사각형(정사각형) 모양의 카펫의 가로 세로 길이를 구하는 문제였다. 우선 사각형 형태이므로 갈색 격자 개수와 노란색 격자 개수를 더한 수는 무조건 짝수가 나올 것이다. 우선 2개를 더한 수의 약수들을 구한다. 

 

그리고 가로의 길이가 더 크므로 i와 곱해서 sum이 나오는 숫자가 가로의 길이가 된다. 그리고 나서 주어진 모양을 만족하는지 검사를 한다. 가로는 2개 이므로 가로 길이에 2를 곱해서 구해주고, 세로도 마찬가지로 2개지만 가로 길이를 구할때 각 사각형의 맨끝을 가로길이에서 이미 포함하고 있기 때문에 4를 빼준다. 그러면  쉽게 답을 구할 수 있다.

class Solution {

    public int[] calRectangle(int brown, int yellow){
        int[] arr = new int[2];
        int sum = brown + yellow;
        for(int i=3;i<=sum;i++){
            if(sum%i == 0){
                Integer x = sum/i; //x가 무조건 더큼, 가로
                int calBrownNum = 2*x + i*2-4;
                if(brown == calBrownNum){
                    arr[0] = x;
                    arr[1] = i;
                    return arr;
                }                
            }
        }
        
        return arr;
    }

    public int[] solution(int brown, int yellow) {
        int[] answer = calRectangle(brown, yellow);
        return answer;
    }
}

3. 다른 사람 풀이

수학적으로 생각해보면 변수가 2개이고 수식이 2개가 있는 형태이다. brown+yellow = 상수, brown*yellow = 상수 이렇게 수식을 놓을 수 있다. 그러면 2차 방정식의 해를 구하는 문제와 똑같아진다. brown = 상수/yellow 이므로 대입하면 상수+yellow^2 = 상수*yellow가 된다.  

import java.util.*;
class Solution {
    public int[] solution(int brown, int red) {
        int a = (brown+4)/2;
        int b = red+2*a-4;
        int[] answer = {(int)(a+Math.sqrt(a*a-4*b))/2,(int)(a-Math.sqrt(a*a-4*b))/2};
        return answer;
    }
}