온코더 제12회차 3번 문제 '격자 칠하기' 풀이

* 온코더 제12회차 3번 문제 '격자 칠하기' 풀이

[ 분류 : 구현/조합/확률 ]

  예전에 못풀었던걸 최근에 확률 공부하다가 생각나서 풀어봤는데 풀려서 기분이 좋다 ㅎㅎ

  문제 요약) N x M 격자에서 총 K번의 연산을 수행한다. 연산은 격자 내부에서 두 칸을 선택하여 두 칸을 양끝으로 하는 사각형 내부에 색을 칠한다. 이 때 칸을 선택하는 확률은 모두 동일하며, 다른 칸을 선택하는 확률과 독립적이다. K번 연산을 모두 끝낸 뒤 칠해진 1 x 1 칸의 개수의 기댓값은 얼마인가?

  해설)

  [확률]

  연산 한 번에 대해서 생각해보자. N x M 격자에서 하나의 칸을 선택하는 경우의 수는 NM 임은 쉽게 알 수 있다. 또한 두 개의 칸을 선택하는 경우의 수는 (NM)^2 이다. 이는 칸 선택이 서로 독립적이기 때문에 바로 구할 수 있다.

  확률론에서 기댓값은 E[X]로 표현한다. 기댓값 자체는 변수로 표현하지 않는 불변량이다. 이 문제의 의도에 맞게 확률 변수 X를

  X = K번 연산 후에 색칠된 칸의 수

로 표현할 수 있다.

  확률 변수 Y(x, y) = K번 연산 이후에 (x, y) 칸이 칠해질 사건 으로 정의하자. 칠해지면 1, 아니면 0으로 보자(단, ).

  X의 기댓값에 대해서 아래와 같이 정리할 수 있으므로 각 칸에 대해서 생각해 볼 필요가 있다.

  확률 p(x, y)를 "1번 연산에서 (x, y)가 포함되는 사각형을 선택할 확률"이라고 하자. 확률 변수 Z(x, y)="K번 연산을 걸쳐 (x, y) 칸이 칠해지는 횟수"라고 하면 Z(x, y)는 이항 분포를 가지게 된다. 동전 앞뒤 나오는 방식과 동일하다고 보면 쉽게 생각할 수 있다.

 우리는 Y(x, y)를 보고 있고, K번 중 단 한 번만 등장해도 된다. 따라서 수식을 아래처럼 정리할 수 있다.

  마지막 식으로 배반 사건을 이용하여 간단하게 구할 수 있다.

  [조합과 구현]

  이제 p(x, y)를 구하러 갑시다. 여기가 구현부분에서 가장 까다로운 부분이 아닐 수 없어요, 조합을 깐깐하게 따져야 합니다.

  사각형을 만들 때 사용되는 두 점을 A, B라고 하면 아래와 같은 상황 모두 따져야 합니다. 같은 크기, 같은 위치의 사각형이라도 그 사각형을 만들 수 있는 경우의 수는 4가지 또는 2가지 또는 1가지로 나올 수 있습니다. 정리하자면 선택된 사각형의 높이가 1보다 크고 너비가 1보다 크면 경우의 수가 4가지 됩니다. 높이와 너비 둘 중 하나만 1보다 큰 상태라면 경우의 수는 2가지 됩니다. A와 B가 완벽하게 같으면 1가지가 나옵니다.

[ 그림 - 같은 크기, 같은 위치를 같은 사각형이 선택되는 경우의 수 ]

(1)	(2)	(3)
(4)	(5) -	(6)
(7)	(8)	(9)

[그림 -  칸에 대한 구역 설정]

  를 포함하는 사각형을 만들기 위한 경우의 수를 구역 별로 나눠봅시다. 구역 별로 두 점을 가져온다면,

  4가지 일 때 = (1) x ((5) + (6) + (8) + (9))

                    + (2) x ((6) + (9))

                    + (4) x ((8) + (9))

                    + (5) x (9)

  2가지 일 때 + 1가지 일 때 = 2가지 x (

                      ((2) + (5)) * ((5) + (8))

                      + ((4) + (5)) * ((5) + (6))

                      ) - 3

  로 정리할 수 있습니다.

  -3을 해주는 이유는 사각형 선택 범위에서 각각 하나를 중복해서 선택하게 되고 이를 2를 곱하기 때문에 "1가지 일 때"의 경우가 4번이나 중첩됩니다. 그래서 -3을 빼주어 계산해줍니다.

- 구현

class Solution{
private:
    double _pow(double a, int n) {
    	if (n <= 1) return n ? a : 1;
    	double h = _pow(a, n >> 1);
    	return h * h * (n % 2 ? a : 1);
    }
public:
    double solution(int K, int rows, int cols){
        double R = rows, C = cols, p, q, rc_2, expectation = 0;
        int i, j;
        rc_2 = R * C * R * C;
        for(i=0;i<R;i++) for(j=0;j<C;j++){
            p = 4 * (
                    i * j * (R - i) * (C - j) // (1) * ((5) + (6) + (8) + (9))
                    + i * (R - i) * (C - j - 1) // (2) * ((6) + (9))
                    + j * (R - i - 1) * (C - j) // (4) * ((8) + (9))
                    + (R - i - 1) * (C - j - 1) // (5) * (9)
                )
                +
                2 * (
                    (i + 1) * (R - i)   // ((2) + (5)) * ((5) + (8))
                    + (j + 1) * (C - j) // ((4) + (5)) * ((5) + (6))
                )
                - 3;
            p /= rc_2;
            
            q = 1 - p;
            expectation += 1 - _pow(q, K);
        }
        
        return expectation;
    }
};