[Programmers] 카펫

https://school.programmers.co.kr/learn/courses/30/lessons/42842

프로그래머스

풀이

분류는 완전탐색인데 푸는건 약수를 이용해서 풀었다. 완탐으로도 풀 수 있을 것 같은데 내가 푼 방식이 더 효율성이 높을 것 같다.

결국 카펫을 이루는 것은 노란색으로 이루어진 판을 갈색으로 한 칸씩 감싸는 것이기 때문에, 노란색이 어떻게 이루어져 있는지 결정하고 가로/세로로 +2씩만 하면 카펫이 구성되는 것을 이용한다.

 

코드

class Solution {
     
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        
        int width = 0, depth = 0;
        for (int i = 1; i <= yellow; i++) {
            if (yellow % i == 0) {
                //yellow가 어떤 모양일지를 yellow의 약수로 구한다.
                //이 때 가로 >= 세로 이므로 yellow를 이루는 두 수중 큰게 가로.
                width = Math.max(i, yellow / i);
                depth = Math.min(i, yellow / i);
                
                //노란색의 가로, 세로에 양끝에 2개씩 붙인게 총 카펫의 개수
                if ((width + 2) * (depth + 2) == brown + yellow) {
                    answer[0] = width + 2;
                    answer[1] = depth + 2;
                    break;
                }
            }    
        }
        
        return answer;
    }
}