프로그래머스 카펫

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

프로그래머스

 

문제 설명 

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

 

 

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

 

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

 

제한사항

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

 

문제 풀이

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        int total = brown + yellow;

        for (int i = 3; i <= total / 3; i++) {
            if (total % i == 0) {
                int j = total / i;
                int yellowCount = (i - 2) * (j - 2);
                
                if (yellow == yellowCount) {
                    answer[0] = Math.max(i, j); // 가로 길이
                    answer[1] = Math.min(i, j); // 세로 길이
                    break;
                }
            }
        }
        
        return answer;
    }
}

해당 문제는 완전 탐색 문제로 모든 경우의 수를 따져봐야 합니다. 이때 경우의 수의 범위를 얼마나 좁힐 수 있는 가가 문제의 의도입니다.

 

for (int i = 3; ...

노란색 격자의 수가 최솟값일 때 갈색 격자의 수의 가로 길이는 최소 3개 이상입니다.

 

for (...; i <= total / 3; ...

가로와 세로 길이가 같은 경우가 최대값을 가질 때이며, 이 때의 가로와 세로 길이는 total의 제곱근 이하입니다. 이를 넘어가는 경우 가로와 세로 길이가 같지 않게 되어 중복 계산이 발생하므로, total의 제곱근 이상의 경우를 고려할 필요가 없습니다.

 

if (total % i == 0)

가로와 세로 길이는 정수값이어야 합니다. 만약 나누어떨어지지 않는 경우가 있다면, 그 경우는 블록을 배치하는 것이 불가능합니다. 정수가 아닌 실수가 가로나 세로 길이가 될 수 없기 때문에, 정수로 나누어떨어지지 않는 경우는 고려할 필요가 없습니다.

 

int yellowCount = (i - 2) * (j - 2);

여기서 i와 j는 각각 가로와 세로 길이를 나타냅니다. 테두리의 두 줄을 뺀 것이므로 가로 길이와 세로 길이에서 각각 2를 빼주고, 이를 곱하여 노란색 칸의 개수를 구합니다.

 

if (yellow == yellowCount)

노란색 블록의 개수는 (i - 2) * (j - 2)로 계산되었습니다. 경우의 수를 돌며 노란색 격자의 수랑 일치할 경우 가로와 세로의 길이가 유효합니다.

 

answer[0] = Math.max(i, j);
answer[1] = Math.min(i, j);

만약 제한사항에 가로의 길이가 더 길다는 말이 없었더라면 가로와 세로 길이를 특정할 수 없었을 겁니다. 세로가 더 길거나, 가로가 길거나 서로 정답일 수 있기 때문입니다. 그러나 가로가 더 길기 때문에 최댓값이 곧 가로 길이입니다