190109 완전탐색 (4) 카펫

2019-01-09

완전 탐색 (4) 카펫

문제 설명

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

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

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

제한사항
  • 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
  • 빨간색 격자의 수 red는 1 이상 2,000,000 이하인 자연수입니다.
  • 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.
입출력 예
brown red return
10 2 [4, 3]
8 1 [3, 3]
24 24 [8, 6]
풀이 과정
  • 갈색 격자 = (가로+세로-2)*2
  • 빨간색 격자 = (가로-2)*(세로-2)
  • 빨간색 격자의 수가 1 이상이려면 카펫은 최소 3*3 크기이다.
  • 가능한 카펫의 크기를 모두 구하면서 갈색격자와 빨간색격자 수가 조건에 맞는지 체크.
class Solution {
    public int[] solution(int brown, int red) {
        int[] answer = new int[2];
        int carpet=brown+red;
        for(int i=3;i<carpet;i++){
            int width=0;
            int height=0;
            if(carpet%i ==0){
                if(i<carpet/i){
                    width=carpet/i;
                    height=i;
                }else{
                    width=i;
                    height=carpet/i;
                }
            }
            if((width+height-2)*2 == brown && (width-2)*(height-2) == red){
                answer[0]=width;
                answer[1]=height;
                break;
            }
        }
        return answer;
    }
}