Table of contents

프로그래머스 카펫

외곽이 갈색 카펫으로 둘러져 있고, 중앙에는 빨간색 카펫이 위치한다. 빨간색 카펫과 갈색 카펫의 개수가 주어졌을 때, 격자 모양 카펫의 가로 세로 길이를 구하는 문제이다.

첫번째 풀이

8개의 갈색 카펫과 1개의 빨간색 카펫이 최소 값이며, 3 * 3의 격자 모양을 갖는다.

왼쪽 화살표가 가로 길이를 증가시키는 부분이고, 오른쪽 화살표가 세로 길이를 증가시키는 부분이다.

각 단계에서 가능한 갈색 타일의 개수와 빨간색 타일의 개수를 찾아보자. 우선 갈색 타일의 경우 여러 방법이 있겠지만 (가로 * 2) + ((세로 - 2) * 2) 의 공식을 발견했다. 빨간색 타일의 경우 (가로 - 2) * (세로 - 2) 로 구할 수 있다.

@Test
public void test() {
    assertThat(solution(10, 2)).isEqualTo(
        new int[]{4, 3}
    );

    assertThat(solution(8, 1)).isEqualTo(
        new int[]{3, 3}
    );

    assertThat(solution(24, 24)).isEqualTo(
        new int[]{8, 6}
    );
}

int[] result;

private int[] solution(int brown, int red) {
    result = new int[2];
    dfs(brown, red, 3, 3);
    return result;
}

private void dfs(int brown, int red, int hori, int vert) {
    int brownCount = (hori * 2) + ((vert - 2) * 2);
    int redCount = (hori - 2) * (vert - 2);

    if (brownCount > brown) {
        return;
    } else if (brown == brownCount && red == redCount) {
        result[0] = hori;
        result[1] = vert;
        return;
    }

    if (hori > vert) {
        dfs(brown, red, hori, vert + 1);
    }

    dfs(brown, red, hori + 1, vert);
}

현재 단계의 갈색 타일의 개수가 사용할 수 있는 갈색 타일의 개수보다 많다면 종료한다. 세로를 증가시키는 단계와 가로를 증가시키는 단계 각각을 재귀로 탐색한다.

시간초과

정답은 구할 수 있지만 시간 초과로 대부분의 테스트 케이스가 깨진다. 완전탐색에 분류되어 모든 경우를 탐색하면 되는가 했더니 갈색 타일의 개수 n과 빨간색 타일의 개수 m의 최대 값이 너무 크다.

또, 탐색이 중복되는 부분이 너무 많다. (5, 3) 단계에서 (5, 4)를 탐색하게 되는데, (4, 4) 단계에서도 (5, 4)를 탐색할 수 있으며 이러한 중복되는 단계의 수는 단계가 증가할수록 배가된다. boolean 배열을 사용해서 방문여부를 표기하기에는 필요없는 코드가 많아져 코드 복잡도가 증가한다.

두번째 풀이

위 그림을 다시 한번 살펴 보자. 세로는 빨간색 타일의 개수 + 2보다 작은 값까지 증가할 수 있다. 빨간색 타일이 1개인 경우 세로가 3까지 증가할 수 있으며 나머지 단계에서도 세로는 해당 범위 내에서 결정된다.

가로의 범위는 세로 보다 크거나 같으며 사용 가능한 갈색 타일의 개수의 범위 내에서 결정된다.

@Test
public void test2() {
    assertThat(solution(14, 4)).isEqualTo(
        new int[]{6, 3}
    );

    assertThat(solution(12, 4)).isEqualTo(
        new int[]{4, 4}
    );
}

private int[] solution(int brown, int red) {
    for (int y = 3; y <= red + 2; y++) {
        for (int x = y; (x * 2) + ((y - 2) * 2) <= brown; x++) {
            if (( x - 2) * (y - 2) == red) {
                return new int[]{x, y};
            }
        }
    }

    return null;
}

같은 개수의 빨간색 타일을 찾더라도, 사용 가능한 갈색 타일의 개수에 따라 격자 모양이 달라진다.

다른 사람의 풀이

private int[] solution2(int brown, int red) {
    int[] result = new int[2];

    int sum = brown + red;
    for (int y = 3; y <= Math.sqrt(brown + red); y++) {
        if (sum % y == 0) {
            int x = sum / y;
            if ((x - 2) * (y - 2) == red) {
                result[0] = x;
                result[1] = y;
                break;
            }
        }
    }

    return result;
}

어떤 사람은 가로를 증가시키면 가능한 빨간색 카펫이 1개 증가하고, 세로를 증가시키면 2배로 증가하는 특징을 이용해서 풀었고, 어떤 사람은 위처럼 사각형의 특징을 이용해 풀었다.

가로 길이는 세로 길이와 모든 타일의 개수에 따라 결정된다. 예를 들어 6 * 4 격자 모양의 모든 타일의 개수는 12개이며 가로 길이 6은 12를 세로 길이 4로 나눈 값이 된다.