프로그래머스 - 완전탐색 - 카펫

programmers.co.kr/learn/courses/30/lessons/42842

코딩테스트 연습 - 카펫

import java.util.Arrays;

public class 카펫 {
    public static void main(String[] args) {
        카펫 o = new 카펫();
        System.out.println(Arrays.toString(o.solution(10, 2)));
    }

    public int[] solution(int brown, int yellow) {
        int[] answer = {};

        int brownWidth = 3;
        int brownHeight = brownWidth+1; // while문에 충족하기위한 임시값 세팅

        while (brownWidth < brownHeight) {
            brownHeight = (brown - brownWidth*2)/2 + 2;
            int yellowWidth = brownWidth - 2;
            int yellowHeight = brownHeight - 2;
            if(yellow == yellowWidth * yellowHeight) {
                answer = new int[]{brownHeight, brownWidth}; // 너비와 높이의 순서를 반대로 출력
                break;
            }
            brownWidth++;
        }

        return answer;
    }
}

알고리즘

• Brute-force
• 갈색 격자의 넓이가 3일때부터 갈색격자의 가로가 세로와 같을때 까지 갈색 격자의 가로,세로 노란 격자의 가로, 세로를 계산하여 구해준다.
• 갈색 격자의 가로와 세로가 같을때까지 하는 이유는 사각형은 가로와 세로를 서로 바꿔도 이 문제에서는 같은 경우라고 볼 수 있기때문에 중복 계산을 피하기 위해서이다.
• 갈색 격자의 넓이는 이미 넓이에 맞춰 가로 세로가 정해졌기 때문에 노란격자의 넓이만 입력받은 값과 같은지 판단하면된다.
• 카펫의 가로가 항상 세로보다 같거나 커야하기 때문에 가로와 세로의 출력 순서를 변경해주면 같은 카펫이 된다.