카펫

https://school.programmers.co.kr/learn/courses/30/lessons/42842

프로그래머스

 

처음엔 완전 탐색으로 풀었다.

 

가로의 길이(x)가 세로의 길이(y)보다 크기 때문에,

1. yellow 카펫의 갯수(x * y)의 제곱근 값을 x로 잡고,

2. 1씩 늘여가며 yellow / x 가 정수가 되는 케이스를 찾아서,

3. 테두리 개수가 brown이 되는 값을 찾았다.

 

class Solution {
    public int[] solution(int brown, int yellow) {
        int sqrt = (int) Math.sqrt(yellow);
        
        int width = 0, height = 0;
        for (int i = sqrt; i <= yellow; i++) {
            if (yellow % i != 0) continue;
            
            int w = i, h = yellow / i;
            
            if (2 * (w + h + 2) == brown) {
                width = w + 2;
                height = h + 2;
                break;
            }
            
        }
        
        return new int[] {width, height};
    }
}

 

그런데 다른 분들의 풀이를 보니 근의 공식으로도 풀리더라..

 

x * y = yellow

(x + 2) * (y + 2) = yellow + brown

 

x, y를 잘 대입해서 풀면 a = 1, b = (4-brown)/2, c = yellow 가 나온다.

 

이를 근의 공식에 대입해서 풀면..

 

 

class Solution {
    public int[] solution(int brown, int yellow) {

        int a = 1, c = yellow, b = (4-brown) / 2;
        
        int h = (-b + (int) Math.sqrt(b * b - 4 * a * c)) / 2*a;

        int w = yellow / h;
        
        if (w > h) return new int[] {w+2, h+2};
        return new int[] {h+2, w+2};
        
    }
    
}

 

그런데 수학 문제 푸는 것도 아니고.. 굳이 근의 공식을 적용해야할까..? 하는 의문이..