[PGS] 카펫 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        int total = brown + yellow;
        
        // 노란색 격자의 수가 1 이상 => 세로 길이는 3이상부터 시작
        for (int h = 3; h < total; h++) {
            int w = total / h;
            
            // 가로가 세로보다 길어야함
            if (w >= h) {
                // 전체 영역의 가로, 세로 - 2 개수 == 노란색 영역의 개수 이면 반환
                if ((h-2) * (w-2) == yellow) {
                    answer[0] = w;
                    answer[1] = h;
                    return answer;
                }
            }
        }
        return answer;
    }
}

📄 해설

접근

• 완전탐색 문제. 격자에 대한 접근을 잘하면 풀 수 있다.
• 격자에 대한 접근은 크게 아래 세가지가 핵심이라고 생각한다.
  1. 구해야 하는 가로, 세로의 길이는 brown + yellow 의 약수이다.
  2. 카펫의 가로/세로 길이 - 2 == 노란 영역의 가로/세로 길이
  3. 가로의 길이 $\geq$ 세로의 길이

과정

• 노란색 격자의 수가 1 이상이므로, 세로 길이 h는 3 이상부터 시작한다. (접근 2로부터 얻을 수 있음)
• 가로의 길이 w 는 brown + yellow / h 로 구한다. (접근 1로부터 얻을 수 있음)
• 가로의 길이가 세로의 길이보다 크거나 같다면, 찾고 있는 값인지 확인한다. (접근 2로부터 얻을 수 있음)