42842 - 카펫

정보

• 문제 보기: 42842 - 카펫
• 소요 시간: 9분 30초
• 풀이 언어: java
• 체감 난이도: 2️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

완전탐색 수학

풀이 코드

정보

• 메모리: 102000 KB
• 시간: 2080 ms

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] ans;
        for (int a = 1; a < 5000; ++a) {
            for (int b = 1; b < 2000000; ++b) {
                if ((2*a + 2*b - 4) == brown && ((a-2)*(b-2) == yellow)) {
                    if (a < b) ans = new int[]{b, a};
                    else ans = new int[]{a, b};
                    return ans;
                } 
            }
        }
        
        return new int[]{-1, -1};
    }
}

풀이 해설

무지성 완탐 때림 (범위에 sqrt 씌우면 좀 더 괜춘할듯?)

⚡ 수학적 최적화

지성있는 $O(1)$ 풀이법은 다음과 같다. (싸피로그가 알고 풀이 쓰기에 참 좋음 ㅇㅅㅇ)

코드로 옮긴거

class Solution {
    public int[] solution(int brown, int yellow) {
        int b4 = brown-4;
        int n = (int)(b4 + Math.sqrt(b4*b4-16*yellow)) >> 2;
        int m = yellow / n;
        
        return new int[]{n+2, m+2};
    }
}

메모

• 사실 완탐으로 풀고 넘기려 했지만 ssaya 님의 명강의(?)를 듣고 상수 풀이 해보기로 함
• 실전에선 그냥 완탐 돌릴듯