[프로그래머스] 카펫 - Java

문제 : 카펫 - 프로그래머스

풀이

간단한 중학교 수학 문제를 코드로 옮겨 풀이하는 문제이다.

주어진 조건

• 테두리 1줄은 모두 갈색이다.
• 테두리 1줄을 제외한 중앙부분은 모두 노란색이다.
• 카펫의 가로 길이는 세로 길이와 같거나 세로 길이보다 길다.
• 갈색으로 칠해진 격자의 수는 8 이상 5,000 이하인 자연수이다.
• 노란색으로 칠해진 격자의 수는 1 이상 2,000,000 이하인 자연수이다.

식 세우기

주어진 카펫의 가로길이가 width, 세로길이가 height 라고 했을 때, 갈색으로 칠해진 격자의 수와 노란색으로 칠해진 격자의 수는 각각 다음과 같은 식으로 나타낼 수 있다.

1. brownCount 갈색으로 칠해진 격자의 수 = (width * 2) + (height - 2) * 2
2. yellowCount 노란색으로 칠해진 격자의 수 = (width - 2) * (height - 2)
3. width * height = brownCount + yellowCount

또, 문제에서 주어진 조건으로부터 가로, 세로 길이의 범위 제한을 찾을 수 있다.

• 노란색으로 칠해진 격자의 수는 1개 이상이다
  → 3 <= width, height→ 3 <= width < brownCount / 2
  → height가 적어도 3 이상이므로 width < brownCount / 2 임을 알 수 있다.
  → 테두리에 속하지 않은 격자가 반드시 1개 이상 존재한다

우리는 여기서 width와 height의 값을 찾아내는 것이므로 이렇게 구한 3 ≤ width < brownCount/2 의 범위 내에서 위 세 가지 식들 중 두 가지를 만족하는 식을 찾으면 답을 알 수 있다.

 

이 때, 문제에 주어진 조건에서 가로 길이는 세로 길이와 같거나 그보다 길다고 하였으므로 가로 길이는 최댓값에서 시작하여 그 값을 줄여나가며 계산하여야 한다.

 

이번 풀이에서는 계산의 편의성과 효율성을 위해서 2번과 3번식을 만족하는 결과를 탐색하였다.

소스코드

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

        for (int width = (brown / 2) - 1; width >= 3; width--) {
            int height = total / width;

            if (width * height != total) {
                continue;
            }

            int yellowCount = (width - 2) * (height - 2);

            if (yellow == yellowCount) {
                return new int[] { width, height };
            }
        }
        return new int[] {}; // 도달해서는 안되는 부분
    }

}

결과