Programmers - 완전탐색 [카펫]

1. 문제

문제 설명

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]

2. 내풀이

import java.util.ArrayList;

public class Carpet {
    public int[] solution(int brown, int yellow) {
        // 전체 박스의 칸수는 갈색 칸수 + 노란색 칸수
        int totalBox = brown + yellow;
        int[] answer= new int[2];
        // 짧은 길이의 변은 최소 2
        int shortLength = 2;
        while (true) {
            // 짧은 길이를 늘려가면서 긴변을 구하고 갈색 칸수와 노란색 칸수가 맞는지 확인
            int longLength = totalBox / shortLength;
            // 갈색칸수는 아래와 같은 조건으로 구할수있다., 노란색은 아래와 같다.
            if((longLength * 2 + shortLength * 2 - 4) == brown && (longLength - 2) * (shortLength - 2) == yellow){
                answer[0] = longLength;
                answer[1] = shortLength;
                // 조건이 맞으면 리턴
                return answer;
            }
            // 아니면 짧은길이를 늘리면서 다시
            shortLength++;
        }
    }

    public static void main(String[] args) {
        Carpet carpet = new Carpet();

        int[] rectangle = carpet.solution(8, 1);
        for (int num:rectangle) {
            System.out.println(num);
        }
    }
}

- 짧은 길이의 변수와 긴 길이의 변수를 구해서 이것들로 갈색칸 수와 노란색 칸수를 구할 수 있다.

- 짧은 길이의 변수를 늘려가면서 조건이 맞으면 리턴

3. 다른 사람 풀이

class Solution {
    public int[] solution(int brown, int red) {
        int[] answer = {};
        answer = new int[2];
        int iAllNum = brown + red;
        int iHeight = 0;

        for (int iBrownWidth = 1; iBrownWidth < brown; iBrownWidth++) {
            iHeight = iAllNum/iBrownWidth;

            if((iBrownWidth-2)*(iHeight-2) == red) {
                answer[0] = iBrownWidth;
                answer[1] = iHeight;
            }
        }
        return answer;
    }
}

- 비슷하다.. 

4. Tip

- 짧은 변의 길이를 구해서 나머지를 구하는 방법으로 조건을 걸어서 짧은 변의 길이를 늘리면서

답을 구한다.