프로그래머스 카펫(자바) - 완전탐색 (약수 구하기)

문제 설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

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

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

제한사항

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

입출력 예brownyellowreturn

10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

---

풀이 

1. 노란색을 갈색이 한줄로 덮고 있다고 했으므로

노란색의 가로 길이 + 2 = 갈색 가로 길이, 노란색의 세로 길이 + 2 = 갈색 세로 길이 이다.

2. 즉, 노란색의 가로, 세로 길이가 결정되면 그에 따라 갈색의 가로, 세로 길이가 결정된다.

3. 노란색은 직사각형을 이루기 때문에 yellow = 노란색 가로 * 세로 길이이다.

즉, yellow의 약수들 중 큰 수와 작은 수의 짝이 노란색의 가로, 세로 길이이다. 예를 들어 yellow가 24라면 (1,24) (2, 12) (3, 8) (4,6) 이 4개가 노란색 가로, 세로 길이가 될 수 있는 것들이다.

4. 노란색의 가로 세로 길이의 후보들을 모두 찾았으므로 그 후보들 중 brown 값을 만족하는 경우를 찾으면 된다.

   노란색 가로 세로 길이를 각각 x, y라고 할 때 brown = (x+2) * 2 + y * 2 으로 구할 수 있다.

 

 

 

소스 코드

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        for (int i = 1; i <= Math.sqrt(yellow); i++) { //약수 구할 때
            if (yellow % i == 0) {
                if ((i+2) * 2 + (yellow/i) * 2 == brown) {
                    answer[1] = i + 2;
                    answer[0] = yellow/i +2;
                }
            }
        }

        return answer;
    }
}