카펫 (programers > lev2 > 완전탐색)

문제 링크

문제설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 빨간색으로 칠해져 있고 모서리는 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

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

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

제한사항

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

입출력 예

풀이

   static public int[] solution(int brown, int red) {
        int[] answer = new int[2];
        
        int sum = brown + red;
        
        for(int i=1; i< (sum/2) ; i++) {
        	if(sum%i == 0) {
        		int p = sum/i;
        		if((p-2)*(i-2) == red) {
        			answer[0] = Math.max(p, i);
        			answer[1] = Math.min(p, i);;
        		}
        		
        	}
        }
   
        return answer;
    }

후기 (1h)

처음에는 red를 중심으로 잡고 brown을 가로x2 + 세로x2 + 4 이런 식으로 생각했는데

red가 4 혹은 6.. 이런식이 될때는 사각형의 방향을 어떻게 잡아줘야 할지 모르겠어서 고민을 했다.

조금 생각해보니 red x brown 은 사각형의 사이즈고 나올 수 있는 (x,y)조합을 찾아준 후,

x-2 * y-2는 red의 개수일때까지 for문으로 반복해주면 되었다.

또 3x4 4x3 등 반복되는 수가 있기 때문에 for문은 절반만 돌려주었다.

식을 생각해내면 금방푸는데 늘 그렇듯 생각하는 게 오래 걸렸다..!^^

tip

1. 두개의 숫자가 나왔을때 대소비교를 해야하는 상황에서 max(a,b) min(a,b)를 해주면 되는 꼼수를 깨닫게 되었다.