[Programmers Lv.2] 카펫

🔗 Link

문제
풀이

💡 Idea

간단한 미지수(w,h)가 2개인 연립 방정식 문제이다.

• 2(w+h) - 4 = brown 개수
• (w-2)*(h-2) = yellow 개수

h를 소거해서 w에 대해서 정리해 주면 다음과 같다.

• (w-2)*(brown/2 - w) = yellow;

또한 h가 w보다 작거나 같이 때문에 다음도 성립한다. ( w >= h = brown/2 + 2 - w;)

• brown/4 + 1 <= w <= brown/2 - 1

이를 통해 w에 대한 이차 방정식을 꺾이지 않는 부분만 탐색하는 문제임을 알 수 있다. 해당 부분에서는 그래프가 convex하지 않기 때문에 parametric search로 풀어주었다.

🔑 Code

class Solution {
    private boolean func(int w, int brown, int yellow){
        return (w-2)*(brown/2 - w) - yellow > 0;
    }
    public int[] solution(int brown, int yellow) {
        int s = brown/4 + 1;
        if((brown%4)>0) s += 1;
        int e = brown/2 - 1;
        
        while(s<e){
            int mid = (s+e)/2;
            // w를 더 키워
            if(func(mid, brown, yellow)){
                s = mid + 1;
            } else {
                e = mid;
            }
        }
        
        return new int[]{e, brown/2 + 2 - e};
    }
}

🗨️ Side Notes