백준 2858번 기숙사 바닥 :: 마이구미

이 글은 백준 알고리즘 문제 2858번 "기숙사 바닥" 을 풀이한다.

문제 풀이는 수학적 접근과 브루트 포스를 활용한다.

문제 링크 - https://www.acmicpc.net/problem/2858

상근이는 기숙사 생활을 한다. 상근이의 방의 크기는 L*W 이다.

수업시간에 타일 채우기 경우의 수를 계산하던 상근이는 자신의 방도 1*1크기 타일로 채우려고 한다. 이 때, 가장자리는 빨간색으로, 나머지는 갈색으로 채우려고 한다.

아래 그림은 상근이의 방의 크기가 4*3일 때 이다.

어느날 상근이네 방에 하근이가 놀러왔다. 하근이는 아름다운 타일 배치에 감동받았다. 다시 방으로 돌아온 하근이는 빨간색과 갈색 타일의 개수는 기억했지만, 방의 크기는 기억해내지 못했다.

빨간색과 갈색 타일의 개수가 주어졌을 때, 상근이 방의 크기를 구하는 프로그램을 작성하시오.

주어지는 입력에 따른 결과는 다음과 같다.

10 2 => 4 3
12 3 => 5 3
14 4 => 6 3
16 9 => 5 5

단순히 생각해도 알 수 있고, 위처럼 적어보아도 알 수 있는 것이 있다.

총 타일의 개수이다.

10 2 => 4 3
= 10 + 2 == 4 * 3

12 3 => 5 3
= 12 + 3 == 5 * 3

먼저 총 타일의 개수를 가질 수 있는 모든 경우를 구한다.

int sum = l + w;
int sqrt = (int) Math.sqrt(sum);

for (int a = 3; a <= sqrt; a++) {
    int b = sum / a;
    // 가로, 세로 => a, b
}

총 타일의 개수의 약수들을 이용하면 올 수 있는 가로, 세로 길이를 알 수 있다.

* 3부터 시작하는 이유는 가로 또는 세로가 2이면 갈색 타일이 올 수 없기 때문이다.

총 타일의 개수를 만들 수 있는 경우를 뽑으면서, 올바른 가로와 세로 길이를 구하면 된다.

올바른 가로와 세로 길이를 구하기 위해서는 다음과 같다.

public boolean isSatify(int a, int b) {
    int brown = b - 2;
    int red = a * b;

    brown = (a - 2) * brown;
    red -= brown;

    if (red == l && brown == w) {
        return true;
    }

    return false;
}

안쪽에 오는 갈색 타일는 가장자리 사이에 존재한다.

결국 갈색 타일은 전체의 각 가로와 세로 길이에서 -2를 한 길이가 된다.

이것을 활용하여 문제를 해결할 수 있다.

static int l, w;
 
private void solve() {
    l = sc.nextInt();
    w = sc.nextInt();
 
    int sum = l + w;
    int sqrt = (int) Math.sqrt(sum);
 
    for (int a = 3; a <= sqrt; a++) {
        int b = sum / a;
 
        if (b <= 2) {
            continue;
        }
 
        if (a * b == sum) {
            if (isSatify(a, b)) {
                if (a > b) {
                    System.out.println(a + " " + b);
                } else {
                    System.out.println(b + " " + a);
                }
 
                return;
            }
        }
    }
}
 
public boolean isSatify(int a, int b) {
    int brown = b - 2;
    int red = a * b;
 
    brown = (a - 2) * brown;
    red -= brown;
 
    if (red == l && brown == w) {
        return true;
    }
 
    return false;
}