카펫

문제정의

---

카펫의 모양이 노란색이 중앙 그 테두리를 갈색이 감싸는 형태이다. 갈색과 노란색 타일이 주어질 때 이 카펫의 모양을 만들기 위한 가로, 세로의 길이를 구하는 문제이다.

문제풀이

---

전체 코드는 다음과 같다.

package level2;

public class Carpet {

    //프로그래머스 문제풀이 level2 카펫

    public static void main(String[] args) {
        int brown = 10;
        int yellow = 2;
        int[] answer = new int[2];
        int sum = (brown+4)/2;
        int h = 3, w = sum -3;
        while(w >= h)
        {
            if((h-2)*(w-2) == yellow)
            {
                answer[0] = w;
                answer[1] = h;
                break;
            }
            h++;
            w--;
        }
    }
    
}

가로 세로 길이를 합친 길이를 sum이라 할 때, 다음과 같이 구할 수 있다. 이 식은 가로x세로-4가 갈색 타일의 합인 식에서 유도했다. 문제에서 yellow는 1이상이므로 가로와 세로길이는 최소 3이상이어야 한다. 따라서 초기 세로의 길이는 3, 가로의 길이는 sum -3으로 한다. 다음으로는 while문을 돌면서 노란타일을 구한다. 노란타일의 수는 사각형 넓이에서 겉 테두리 영역을 제외한 것이므로 각각의 길이에 -2를 하여 구한다. 이 수가 문제에 주어진 노란타일의 수와 일치하면 가로와 세로 값을 배열에 담아 반환한다.

이 문제의 시간복잡도는 w의 초기 길이를 n이라 할 때, \(O(n)\)이다.

테스트