프로그래머스_완전탐색_카펫 (JAVA)

문제 설명 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 빨간색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.     Leo는 집으로 돌아와서 아까 본 카펫의 빨간색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다. Leo가 본 카펫에서 갈색 격자의 수 brown, 빨간색 격자의 수 red가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.   제한사항 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다. 빨간색 격자의 수 red는 1 이상 2,000,000 이하인 자연수입니다. 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

 

 

레벨2의 마지막 문제로 돼있어 어려운 문제가 나올 줄 알았는데 쉬어가는 곳이었습니다. 그림을 조금 그려보면 어렵지 않게 풀 수 있을 것 같습니다. 이것도 완전탐색이라 부를 수 있는지는 잘 모르겠습니다. 

 

 

---

 

 

일단 가로 세로의 길이부터 확인해보면 됩니다. 가로의 블럭 갯수와 세로의 블럭 갯수는 겹치는 부분이 모서리의 4개이므로 전체 brown의 갯수는 "2x + 2y - 4" 입니다.

 

그리고 가로축이 세로축보다 크거나 같다고 했으므로 세로축을 작은 숫자부터 증가시키면서 가로축의 길이를 산정하면 됩니다. red가 최소 1개가 있기 때문에 세로 블럭은 3개 미만이 될 수 없어 3부터 시작합니다. 

 

그리고 red의 갯수는 (x-2) * (y-2)이기 때문에 산정된 가로 세로 블럭 수에서 계산된 red 갯수와, 주어진 red 갯수를 비교해 같을 때는 찾으면 됩니다.

 

package pojoPrj;

import java.util.Arrays;

class Solution {

	public int[] solution(int brown, int red) {

		int height = 0;
		int width = 0;
		for (height = 3; height <= (int) (brown + 4) / 2; height++) {

			width = ((brown + 4) / 2) - height;
			if (width < height) {
				break;
			}

			int redCount = (width - 2) * (height - 2);
			if (red == redCount) {
				break;
			}
		}

		int[] answer = new int[] { width, height };
		return answer;
	}
}