[프로그래머스] Lv2. 카펫, 완전탐색

문제 설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

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

입출력 예

brown yellow return

10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

풀이

접근하기

가로와 세로는 항상 모서리 4개는 공유하고 있음

brown과 yellow 의 숫자가 주어짐

가로 X ≥ 세로 Y !!

예시를 참고해보면

brown 개수 = 2X + 2Y - 4 ( 전체 가로 세로에서 모서리 다 뺀값)

yellow의 가로길이는 x-2 보다 같거나 작음

yellow의 세로길이는 y-2 보다 같거나 작음

yellow 개수 ≤ (x-2) * (y-2)

미완성 코드

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = {};       
        int x = 0; //가로 
        int y = 0; //세로       
        //가로가 brown/2보다 클수없음!
        for(int i = 1; i < brown/2; i++){
            x = i;
            for(int j = 0; j <= i; j ++) { //y는 항상 x보다 작거나같음
               y = j; 
                int brown_lim = 2*x+ 2*y - 4;
                int yellow_lim = (x-2) * (y-2);
                if(brown_lim == brown && yellow_lim >= yellow) {
                    x = i;
                    y = j;                    
                    System.out.println("x는?" + x);
                    System.out.println("y는?" + y);          
                }
            }
        }        
        return answer;
    }
}

위 조건들로만 구현하면 test3에서 예외가 발생함 test1,2만 만족함

맨 마지막 조건을 생각해보니

brown + yellow = 가로 * 세로 이다

전체 갯수 = 가로 * 세로 인 셈,,

이를 추가해주니 쉽게 답이 나왔따!

정답 코드

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        int x = 0; //가로 
        int y = 0; //세로       
        //가로가 brown/2보다 클수없음!
        for(int i = 1; i < brown/2; i++){
            x = i;
            for(int j = 0; j <= i; j ++) { //y는 항상 x보다 작거나같음
               y = j; 
                int brown_lim = 2*x+ 2*y - 4;
                int yellow_lim = (x-2) * (y-2);
                int gatsu = brown + yellow;
                int hap = x * y;
                if(brown_lim == brown && yellow_lim >= yellow && hap == gatsu) {
                    x = i;
                    y = j;                    
                    answer[0] = x;
                    answer[1] = y;
                }
            }
        }
        
        return answer;
    }
}