[Java Algorithm] 프로그래머스 Lv.2_ 카펫

[문제]

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.
Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.
Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항
- 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
- 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
- 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

 

[Algorithm]

전체 카펫 개수를 구하고 (brown + yellow) 가능한 세로 길이를 3부터 √total까지 반복

각 세로 길이에 대해 가로 길이 계산 (total / height)

계산된 노란색 영역이 주어진 yellow랑 일치하는지 확인

 

[Code]

class Solution {
    public int[] solution(int brown, int yellow) {
        int total = brown + yellow;
        
        for(int h = 3; h <= Math.sqrt(total); h++) {
            if(total % h == 0) {
                int w = total / h;
                
                int yellowCount = (w - 2) * (h - 2);
                
                if(yellowCount == yellow) {
                    return new int[]{w, h};
                }
            } 
        }
        return new int[]{0, 0};
    }
}

 

[+ 다른 사람 풀이]

import java.util.*;

class Solution {
    public int[] solution(int brown, int yellow) {
        int a = (brown+4)/2;
        int b = yellow+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;
    }
}

 

이건 문제 개편 이전 풀이인데 뭐가 정확히 달라진지는 모르겠음 ..

위 코드는 근의 공식을 이용한 코드

노란색 카펫 공식을 전개하면

(width-2) × (height-2) = yellow
width × height - 2×width - 2×height + 4 = yellow
(brown + yellow) - 2×(width + height) + 4 = yellow
brown + 4 = 2×(width + height)

 

 

따라서 width + height = (brown + 4) / 2

 

int a = (brown+4)/2;  // a = width + height
int b = yellow+2*a-4;  // 이차방정식의 상수항

 

b 값은 다음과 같이 유도

width × height = brown + yellow

width + height = a이므로

이차방정식: x² - ax + (brown + yellow) = 0에서

width × height = yellow + 2a - 4로 변형된 형태

 

int[] answer = {
    (int)(a+Math.sqrt(a*a-4*b))/2,  // 더 큰 값 (가로)
    (int)(a-Math.sqrt(a*a-4*b))/2   // 더 작은 값 (세로)
};

이차방정식 x² - ax + b = 0의 해

→ x = (a ± √(a² - 4b)) / 2